public class AdjacencyMatrix
{
    private int[,] matrix;
    private int vertices;
    
    public AdjacencyMatrix(int v)
    {
        vertices = v;
        matrix = new int[v, v];
    }
    
    // Thêm cạnh vô hướng
    public void AddEdge(int source, int dest)
    {
        matrix[source, dest] = 1;
        matrix[dest, source] = 1;
    }
    
    // Thêm cạnh có hướng
    public void AddDirectedEdge(int source, int dest)
    {
        matrix[source, dest] = 1;
    }
    
    // Kiểm tra cạnh tồn tại
    public bool HasEdge(int source, int dest)
    {
        return matrix[source, dest] == 1;
    }
    
    // In ma trận kề
    public void PrintMatrix()
    {
        for (int i = 0; i < vertices; i++)
        {
            for (int j = 0; j < vertices; j++)
            {
                Console.Write(matrix[i,j] + " ");
            }
            Console.WriteLine();
        }
    }
}

public class WeightMatrix
{
    private int[,] matrix;
    private int vertices;
    private const int INF = int.MaxValue;
    
    public WeightMatrix(int v)
    {
        vertices = v;
        matrix = new int[v, v];
        
        // Khởi tạo với giá trị vô cùng
        for (int i = 0; i < v; i++)
            for (int j = 0; j < v; j++)
                matrix[i,j] = INF;
    }
    
    // Thêm cạnh có trọng số
    public void AddEdge(int source, int dest, int weight)
    {
        matrix[source, dest] = weight;
        matrix[dest, source] = weight;
    }
    
    // Thêm cạnh có hướng và trọng số
    public void AddDirectedEdge(int source, int dest, int weight)
    {
        matrix[source, dest] = weight;
    }
    
    // Lấy trọng số cạnh
    public int GetWeight(int source, int dest)
    {
        return matrix[source, dest];
    }
    
    // In ma trận trọng số
    public void PrintMatrix()
    {
        for (int i = 0; i < vertices; i++)
        {
            for (int j = 0; j < vertices; j++)
            {
                if (matrix[i,j] == INF)
                    Console.Write("∞ ");
                else
                    Console.Write(matrix[i,j] + " ");
            }
            Console.WriteLine();
        }
    }
}

public class AdjacencyList
{
    private List<int>[] adjList;
    private int vertices;
    
    public AdjacencyList(int v)
    {
        vertices = v;
        adjList = new List<int>[v];
        for (int i = 0; i < v; i++)
            adjList[i] = new List<int>();
    }
    
    // Thêm cạnh vô hướng
    public void AddEdge(int source, int dest)
    {
        adjList[source].Add(dest);
        adjList[dest].Add(source);
    }
    
    // Thêm cạnh có hướng
    public void AddDirectedEdge(int source, int dest)
    {
        adjList[source].Add(dest);
    }
    
    // Kiểm tra cạnh tồn tại
    public bool HasEdge(int source, int dest)
    {
        return adjList[source].Contains(dest);
    }
    
    // In danh sách kề
    public void PrintGraph()
    {
        for (int i = 0; i < vertices; i++)
        {
            Console.Write($"Đỉnh {i}: ");
            foreach (int v in adjList[i])
            {
                Console.Write($"{v} ");
            }
            Console.WriteLine();
        }
    }
}

public class WeightedAdjacencyList
{
    private class Edge
    {
        public int Dest;
        public int Weight;
        
        public Edge(int d, int w)
        {
            Dest = d;
            Weight = w;
        }
    }
    
    private List<Edge>[] adjList;
    private int vertices;
    
    public WeightedAdjacencyList(int v)
    {
        vertices = v;
        adjList = new List<Edge>[v];
        for (int i = 0; i < v; i++)
            adjList[i] = new List<Edge>();
    }
    
    // Thêm cạnh có trọng số
    public void AddEdge(int source, int dest, int weight)
    {
        adjList[source].Add(new Edge(dest, weight));
        adjList[dest].Add(new Edge(source, weight));
    }
    
    // Thêm cạnh có hướng và trọng số
    public void AddDirectedEdge(int source, int dest, int weight)
    {
        adjList[source].Add(new Edge(dest, weight));
    }
    
    // Lấy trọng số cạnh
    public int GetWeight(int source, int dest)
    {
        foreach (Edge e in adjList[source])
        {
            if (e.Dest == dest)
                return e.Weight;
        }
        return -1; // Không tồn tại cạnh
    }
    
    // In danh sách kề có trọng số
    public void PrintGraph()
    {
        for (int i = 0; i < vertices; i++)
        {
            Console.Write($"Đỉnh {i}: ");
            foreach (Edge e in adjList[i])
            {
                Console.Write($"({e.Dest},{e.Weight}) ");
            }
            Console.WriteLine();
        }
    }
}

public class EdgeList
{
    private class Edge
    {
        public int Source;
        public int Dest;
        public int Weight;
        
        public Edge(int s, int d, int w = 1)
        {
            Source = s;
            Dest = d;
            Weight = w;
        }
    }
    
    private List<Edge> edges;
    private int vertices;
    
    public EdgeList(int v)
    {
        vertices = v;
        edges = new List<Edge>();
    }
    
    // Thêm cạnh
    public void AddEdge(int source, int dest, int weight = 1)
    {
        edges.Add(new Edge(source, dest, weight));
    }
    
    // Kiểm tra cạnh tồn tại
    public bool HasEdge(int source, int dest)
    {
        return edges.Any(e => e.Source == source && e.Dest == dest);
    }
    
    // In danh sách cạnh
    public void PrintEdges()
    {
        foreach (Edge e in edges)
        {
            Console.WriteLine($"{e.Source} -> {e.Dest} (w={e.Weight})");
        }
    }
}