Biểu diễn đồ thị

Cho đồ thị có hướng \(G = (E, V)\) gồm \(N\) đỉnh và \(M\) cạnh. Hãy in ra ma trận kề của \(G\)

Input

• Dòng đầu tiên gồm 2 số nguyên \(N\), \(M\) (\(N \leq 50\), \(M \leq 50\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v\) thể hiện cung nối từ đỉnh \(u\) đến đỉnh \(v\)

Output

In ra một ma trận gồm \(N\) hàng, \(N\) cột. Ô \((i, j)\) là \(0\) nếu không có cạnh nối \(i-j\), là \(1\) nếu có cạnh nối \(i-j\)

Example:

Sample input

3 4
1 2
2 3
3 1
2 1

Sample output

0 1 0
1 0 1
1 0 0

Cho đồ thị có hướng \(G = (E, V)\) gồm \(N\) đỉnh và \(M\) cạnh. Hãy in ra danh sách kề của mỗi đỉnh theo thứ tự tăng dần

Input

• Dòng đầu tiên gồm 2 số nguyên \(N\), \(M\) (\(N \leq 50\), \(M \leq 50\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v\) thể hiện cung nối từ đỉnh \(u\) đến đỉnh \(v\)

Output

In ra \(N\) dòng, mỗi dòng là danh sách kề của đỉnh \(i\) theo thứ tự tăng dần (in ra \(0\) nếu danh sách kề của \(i\) rỗng)

Example

Sample input

3 4
1 2
2 3
3 1
2 1

Sample output

1: 2
2: 1 3
3: 1

Cho đồ thị vô hướng \(G = (E, V)\) gồm \(N\) đỉnh và \(M\) cạnh. Từ đồ thị \(G\), tạo ra một đơn đồ thị \(G' = (E', V')\).
Hãy in ra danh sách kề theo thứ tự tăng dần của đỉnh \(i\) trong đồ thị \(G'\)

(Đơn đồ thị là đồ thị không có khuyên và không có cạnh song song)

Input

• Dòng đầu tiên gồm 2 số nguyên \(N\), \(M\) (\(N \leq 50\), \(M \leq 50\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v\) thể hiện cung nối từ đỉnh \(u\) đến đỉnh \(v\)

Output

In ra \(N\) dòng, mỗi dòng là danh sách kề của đỉnh \(i\) theo thứ tự tăng dần (in ra \(0\) nếu danh sách kề của \(i\) rỗng)

Ví dụ:

Sample Input

3 4
1 3
2 3
1 1
2 3

Sample Output

1: 3 
2: 3 
3: 1 2

Cho đơn đồ thị vô hướng (không có khuyên) \(G = (E, V)\) gồm \(N\) đỉnh và \(M\) cạnh. Hãy in ra số bậc của \(N\) đỉnh

Input

• Dòng đầu tiên gồm 2 số nguyên \(N\), \(M\) (\(N \leq 50\), \(M \leq 50\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v\) thể hiện cung nối từ đỉnh \(u\) đến đỉnh \(v\)

Output

In ra \(N\) số, số thứ \(i\) là bậc của đỉnh \(i\)

Example

Sample Input

4 4
1 2
2 3
3 1
2 4

Sample Output

2 3 2 1

Cho đồ thị có hướng có trọng số gồm \(N\) đỉnh và \(M\) cạnh. Hãy in ra danh sách cạnh theo thứ tự trọng số tăng dần (nếu trọng số bằng nhau thì sắp xếp theo thứ tự xuất hiện).

Input

• Dòng đầu tiên gồm 2 số nguyên \(N\), \(M\) (\(N \leq 50\), \(M \leq 50\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v, c\) thể hiện cung nối từ đỉnh \(u\) đến đỉnh \(v\) có trọng số \(c\)

Output

In ra \(M\) dòng, mỗi dòng là thông tin của của cạnh thứ \(i\) sau khi được sắp xếp

Example

** Sample Input **

4 4
1 3 2
3 4 8
2 3 4
1 4 1

**Sample Output **

1 4 1
1 3 2
2 3 4
3 4 8

"Nhất tiễn" BaoJiaoPisu là tài năng trẻ được kì vọng của đội Tin Đà Nẵng. BaoJiaoPisu đang tập luyện hăng say để chuẩn bị màn combat code với "Song điêu" của Tam Kì. Nhưng vì đang mơ tưởng đến chiến thắng trước mắt, BaoJiaoPisu không thể tập trung cho bài tập về nhà của Facebook được. Các bạn hãy giúp BaoJiaoPisu hoàn thành bài tập này sớm để cậu có thể thoải mái tập trung cho trận combat sắp tới nhé.

Trong 1 group trên Facebook có \(n\) người, \(m\) cặp bạn khác nhau. Cho \(q\) truy vấn, mỗi truy vấn gồm 2 số \(s, t\). Ở mỗi truy vấn, hãy cho biết số bạn chung của 2 người \(s, t\) là bao nhiêu?

Input

• Dòng đầu tiên gồm 2 số nguyên \(n\), \(m\) (\(n \leq 1000\), \(m \leq \dfrac{n(n - 1)}{2}\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v\) thể hiện 2 người \(u, v\) là bạn bè của nhau
• Dòng tiếp theo gồm số nguyên \(q\) (\(q \leq 1000\))
• Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(s, t\) (\(1 \leq s, t \leq n\))

Output

In ra \(Q\) dòng, mỗi dòng là kết quả của truy vấn thứ \(i\)

Example

Sample Input

5 4
5 3
2 5
1 4
5 1
2
5 3
4 5

Sample Output

0
1