Reprezentacja grafu

Limit czasu: 1s | Limit pamięci: 64MB

Istnieją dwa standardowe sposoby reprezentacji grafu $G = (V, E)$ w pamięci komputera: listy sąsiedztwa (ang. adjacency lists) oraz macierz sąsiedztwa (ang. adjacency matrix).

Reprezentacja listw sąsiedztwa składa się z tablicy $adj$ zawierającej $|V|$ list, po jednej dla każdego wierzchołka. Dla każdego $u \in V$ lista sąsiedztwa $adj[u]$ zawiera wszystkie wierzchołki $v$ takie, że istnieje krawędź $(u, v) \in E$. Oznacza to, że $adj[u]$ składa się ze wszystkich wierzchołków sąsiadujących z $u$ w $G$.

Reprezentacja macierzy sąsiedztwa składa się z macierzy $A = [a_{ij}]$ o wymiarach $|V| \times |V|$ takiej, że $a_{ij} = 1$ jeśli $(i, j) \in E$ oraz $a_{ij} = 0$ w przeciwnym razie.

Napisz program, który wczytuje graf skierowany $G$ reprezentowany przez listy sąsiedztwa i wyświetla jego reprezentację w postaci macierzy sąsiedztwa. $G$ składa się z $n$ wierzchołków o identyfikatorach: $1, 2, \ldots, n$.

Wejście

W pierwszym wierszu podana jest liczba całkowita $n$. W kolejnych wierszach $n$ lista sąsiedztwa $adj[u]$ dla wierzchołka $u$ jest podana w następującym formacie:

$u$ $k$ $v_1$ $v_2$ ... $v_k$

$u$ to identyfikator wierzchołka, $k$ oznacza liczbę krawędzi wychodzących z tego wierzchołka, $v_i$ to identyfikatory wierzchołków sąsiadujących z $u$.

Wyjście

Wypisz reprezentację grafu $G$ w postaci macierzy sąsiedztwa. Umieść pojedynczy znak spacji pomiędzy $a_{ij}$

Ograniczenia

• $1 \leq n \leq 100$

Przykłady

Wejście 1

4
1 2 2 4
2 1 4
3 0
4 1 3

Wyjście 1

0 1 0 1
0 0 0 1
0 0 0 0
0 0 1 0