Đồ thị: BFS và DFS (vận dụng cao)

Đồ 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

Bên cạnh sở thích ngồi ngắm kiến vào giờ rãnh thì ông \(Z\) còn có một sở thích khác đó chính là làm toán.

Sau hàng giờ đống hồ ngồi ngoài vườn, ông \(Z\) tìm đến chiếc bàn làm việc của mình để giải các bài toán. Hôm nay, ông lại tiếp tục làm toán nhưng làm một mình mãi cũng chán nên ông \(Z\) đã quyết định mời các bạn cũng làm toán với ông ấy. Sau đây là bài toán mà ông \(Z\) muốn thử thách các bạn.

Cho dãy \(S\) gồm có \(N\) chữ số (\(N \le 10\)). Các bạn hãy tìm một số nguyên dương nhỏ nhất chia hết cho \(k\) được tạo từ các số thuộc dãy \(S\).

Input

• Dòng đầu tiên gồm 2 số \(N\) và \(k\) (\(k \le 5 \times 10^5\))
• Dòng tiếp theo gồm \(N\) chữ số

Output

• Gồm \(1\) số nguyên dương duy nhất thỏa mãn yêu cầu, nếu ko có số thỏa mãn in ra \(-1\).

Example

2 12
1 4

144

Một Trung tâm nghiên cứu tuyệt mật (mà chúng ta không có quyền nói rõ tên ở đây) có \(n\) phòng thí nghiệm đặt ngầm trong lòng đất. Các phòng thí nghiệm được đánh số từ 1 đến \(n\) (\(1 \leq n \leq 10^{5}\)). Giữa một số phòng có đường hầm nối với nhau, sao cho từ một phòng bất kỳ có thể đi đến phòng bất kỳ khác (có thể phải đi qua một số phòng nào đó). Độ dài mỗi đường hầm là như nhau và thời gian đi hết một đường hầm là 1. Không có đường hầm nào nối một phòng với chính nó, nhưng có thể có nhiều đường hầm cùng nối 2 phòng với nhau và tổng cộng trong Trung tâm có tất cả \(m\) đường hầm (\(1 \leq m \leq 10^{5}\)). Đường hầm cho phép đi lại theo cả hai chiều. Có \(k\) phòng có lối thoát hiểm lên mặt đất (\(1 \leq k \leq n\)). Trong trường hợp sơ tán khẩn cấp, tất cả các nhân viên phải tập trung ở những phòng có lối thoát hiểm.

Yêu cầu:

Hãy xác định thời gian tối thiểu để nhân viên mỗi phòng tập trung về phòng có lối thoát hiểm trong trường hợp phải sơ tán khẩn cấp.

Input:

• Dòng đầu tiên chứa 2 số nguyên \(n\) và \(k\)

• Dòng thứ 2 chứa \(k\) số nguyên khác nhau cho biết các phòng có cửa thoát hiểm

• Dòng thứ 3 chứa số nguyên \(m\), mỗi dòng trong \(m\) dòng tiếp theo chứa 2 số nguyên xác định cặp phòng có đường hầm nối trực tiếp.

Output:

• Một dòng chứa \(n\) số nguyên, số thứ \(i\) xác định thời gian tối thiểu để nhân viên phòng \(i\) đi được tới phòng có lối thoát hiểm

Example

10 2
10 8
9
6 7
7 5
5 8
8 1
1 10
10 3
3 4
4 9
9 2

1 4 1 2 1 3 2 0 3 0

Tới thời điểm hiện tại, \(Z\) đã là ông chủ sở hữu của một cửa hàng bóng chứa vô số những quả bóng bay. Vào một ngày ông \(Z\) muốn đa dạng hóa kho bóng của ông nên ông đã đặt \(N\) đơn hàng đến nhà cung cấp.

Ban đầu tất cả bóng của ông có đều có chung một màu, mặc định là màu \(0\). Hôm nay có \(N\) xe tải tới giao bóng có dạng \((x, y)\). Số bóng bay được giao bởi mỗi xe tải cũng là vô số và tất cả chúng sẽ có chung một màu \(y\). Mỗi quả bóng màu sẽ được thêm vào ngay sau màu \(x\). Nếu màu \(x\) không có sẵn trong kho thì số bóng trong lần giao này sẽ được chuyển về lại cho nhà cung cấp.

Số lượng bóng được giao quá lớn nên chỉ một mình ông \(Z\) thì khó có thể quản lý được hết. Vì vậy ông chủ đã nhờ đến sự giúp đỡ của các bạn. Ông ấy muốn biết được màu của tất cả quả bóng thuộc nửa đoạn \((L, R]\) sau khi nhận được \(N\) đơn hàng.

Input

• Dòng đầu tiên gồm \(3\) số: số lượt giao hàng \(N\) (\(N \le 2 \times 10^5\)) và đoạn \((L, R]\) (\(0 \le L < R \le 10^6 , R – L \le 10^5\)).
• \(N\) dòng tiếp theo: mỗi dòng gồm \(2\) số \(x\) và \(y\) (\(0 \le x, y < 2 \times 10^5\)).

OUtput

• Gồm một dòng duy nhất in ra tất cả bóng bay thuộc đoạn \((L, R]\).

Example

4 1 6
0 1
1 3
0 1
1 2

1 2 1 2 3

Đất nước Byteland có \(n\) thành phố được đánh số từ \(1\) đến \(n\). Các thành phố này được kết nối với nhau bởi \(n + 1\) con đường hai chiều. Hệ thống đường hai chiều được xây dựng để đảm bảo rằng từ một thành phố bất kỳ ta có thể di chuyển trực tiếp hoặc gián tiếp đến mọi thành phố còn lại, và không tồn tại cặp thành phố nào được kết nối trực tiếp bởi hai (trở lên) con đường khác nhau.

Nhàn và Nhi là một cặp doanh nhân rất nhiệt huyết và hào phóng. Mỗi người đều muốn thuê trọn một con đường để tổ chức lễ hội ẩm thực đường phố cho người dân Byteland. Hai con đường được thuê đều sẽ bị phong tỏa và xe cộ không thể di chuyển qua lại. Nhà chức trách Byteland liền nhờ Lương lập trình tính số phương án cho thuê khác nhau để \(n\) thành phố tiếp tục liên thông với nhau. Nói cách khác, hãy đếm số cặp đường đi hai chiều khác nhau để khi bỏ chúng ra thì từ một thành phố bất kỳ ta vẫn có thể di chuyển đến mọi thành phố còn lại. Lương đang rất bận bịu với học kỳ mới nên các bạn hãy giúp anh ấy nhé!

Input

• Dòng đầu tiên gồm số nguyên dương \(n\) (\(4 \leq n \leq 10^5\))
• \(n + 1\) dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương \(u, v\) thể hiện đường đi 2 chiều từ thành phố \(u\) tới \(v\) (\(1 \leq u, v \leq n, u \neq v\))

Output

• In ra số nguyên duy nhất là số lượng phương án thỏa mãn

Scoring

• Subtask 1: \(\ n \leq 100\)
• Subtask 2: \(\ n \leq 5000\)
• Subtask 3: \(\ n \leq 10^5\)

Example

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

8