Đồ thị 1b: 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

Đồ thị: Gồm một tập các đỉnh được nối với nhau bằng các cạnh. Nếu không không được chỉ rõ trong ngữ cảnh, đồ thị được hiểu là đồ thị đơn.

Liên thông: Nếu giữa hai điểm bất kỳ của một đồ thị đều có thể thiết lập một đường đi từ đỉnh này đến đỉnh kia, đồ thị được coi là liên thông; nếu không, đồ thị được coi là không liên thông. Một đồ thị được coi là hoàn toàn không liên thông nếu không có đường đi giữa hai đỉnh bất kỳ trong đồ thị. Đây chỉ là một cái tên khác để miêu tả một đồ thị rỗng hoặc một tập độc lập.

Yêu cầu: Cho đơn đồ thị vô hướng \(G = (V, E)\) gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ \(1\) tới \(n\) và các cạnh được đánh số từ \(1\) tới \(m\). Tìm số thành phần liên thông của đồ thị.

Input

• Dòng 1: Chứa hai số \(n, m\).

• \(M\) dòng tiếp theo: Dòng thứ \(i\) có dạng 2 số nguyên \(u, v\). Trong đó \(u, v\) là chỉ số hai đỉnh đầu mút của cạnh thứ \(i\).

Output

• Ghi số \(k\) là số thành phần liên thông của đồ thị.

Constraints

• \(1 \leq n \leq 100000\)
• \(1 \leq m \leq 100000\)

Example

7 6
1 2
1 3
2 3
5 6
6 7
5 7 

3

Cho một đồ thị vô hướng gồm \(N\) đỉnh đánh số từ 1 tới \(N\) và \(M\) cạnh. Độ dài của mỗi cạnh có giá trị là 1. Một đồ thị sẽ có 1 nút trung tâm \(S\).

Yêu cầu

Với mỗi đỉnh có thể tới được từ đỉnh \(S\), tính khoảng cách ngắn nhất từ đỉnh đó tới \(S\) và in ra các đỉnh theo thứ tự khoảng cách ngắn nhất tăng dần. Lưu ý: nếu 2 đỉnh có khoảng cách bằng nhau thì nhãn nào nhỏ hơn sẽ đứng trước.

Input

• Dòng đầu gồm 3 số nguyên \(N, M, S\) (\(N \leq 10^5, M \leq 10^5, 1 \leq S \leq N\))
• \(M\) dòng sau mỗi dòng gồm 2 số thể hiện 2 đầu của một cạnh.

Output

• In ra số dòng tương ứng với số đỉnh có thể tới được từ \(S\) theo thứ tự khoảng cách ngắn nhất tăng dần.
• Trên mỗi dòng in ra nhãn của đỉnh đó và khoảng cách ngắn nhất của đỉnh đó tới \(S\).

Example

7 6 1
1 2
2 3
3 4
4 5
5 6
1 3 

1 0
2 1
3 1
4 2
5 3
6 4