Saba1000kg

Xem PDF



Thời gian:
Java 4.0s
Python 5.0s
Bộ nhớ:
Python 512M

Tác giả:
Dạng bài
Điểm: 400 (p) Thời gian: 1.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho đồ thị vô hướng gồm \(N\) đỉnh và \(E\) cạnh. Xét \(P\) đồ thị con trong đồ thị đó, tập đỉnh của mỗi đồ thị con là một tập con trong tập đỉnh của đồ thị gốc, và tập cạnh của đồ thị con chính là tập tất cả các cạnh nối hai đỉnh bất kỳ trong tập đỉnh con đó. Hãy đếm xem những đồ thị con đó có bao nhiêu thành phần liên thông.

Input

  • Dòng đầu tiên chứa số ba nguyên \(N\), \(E\)\(P\) (\(1\leq N,P\leq 10^5,0\leq E\leq 10^5\)).
  • \(E\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u\)\(v\) (\(u≠v\)) thể hiện một cạnh nối trực tiếp giữa hai đỉnh \(u\)\(v\) trong đồ thị.
  • \(P\) dòng tiếp theo mô tả các đồ thị con của đồ thị đã cho. Mỗi dòng bắt đầu bằng số lượng đỉnh trong tập đỉnh con và theo sau bởi các đỉnh tương ứng.
  • Tổng kích thước của các tập đỉnh con không vượt quá \(10^5\).

Output

  • Gồm \(P\) dòng, mỗi dòng chứa một số nguyên là số thành phần liên thông trong đồ thị con tương ứng.

Example

Test 1

Input
4 4 3
1 2
3 1
1 4
3 4
3 2 3 4
1 1
4 1 2 3 4
Output
2
1
1

Test 2

Input
5 1 1
1 2
5 5 4 3 2 1
Output
4

Nguồn bài: CERC 2019


Bình luận

Không có bình luận nào.