TOUR - Tham quan những cây cầu
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: trungvt130584

Quốc đảo ByteLand nổi tiếng trên thế giới về những cây cầu vượt biển của mình. Việc thực hiện các tour du lịch tham quan những cây cầu là một trong những niềm vui chính của du khách mỗi khi đến quốc đảo. Tuy nhiên theo Euler, người đã giải bài toán nổi tiếng "Bảy cây cầu ở Konigsberg", thì không thể tham quan tất cả những cây cầu của quốc đảo này chỉ trong một tour du lịch được. Thay vào đó, mỗi du khách phải thực hiện nhiều tour du lịch mới hy vọng tham quan được hết những cây cầu.nay

ByteLand có N hòn đảo xinh đẹp và có N-1 cây cầu vượt biển nối các hòn đảo này với nhau sao cho từ một đảo bất kỳ luôn có thể đi đến hòn đảo bất kỳ khác chỉ bằng cách sử dụng các cây cầu này.

Lần đầu tiên đến ByteLand, Bờm rất muốn tham quan tất cả các cây cầu. Tuy nhiên, với bản tính hấp tấp vốn có của mình, anh ta chọn ngay m tour du lịch đầu tiên mà công ty du lịch quảng cáo (vì Bờm chỉ có đủ tiền để đi m tour du lịch). Mỗi tour du lịch thực hiện việc tham quan tất cả các cây cầu từ đảo a đến đảo b nào đó.

Nộp tiền xong rồi, Bờm mới giật mình tự hỏi: "Có còn cây cầu nào mà mình không tham quan khi thực hiện xong m tour du lịch này nhỉ?".

Viết chương trình xác định số lượng các cây cầu mà Bờm không tham quan được.

Dữ liệu nhập:

- Dòng thứ nhất ghi số nguyên N - số hòn đảo (1 ≤ N ≤ 200.000)
- N - 1 dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b - có một cây cầu vượt biển nối đảo a và đảo b.
- Dòng thứ N + 1 ghi số nguyên M - số tour du lịch mà Bờm đăng ký (1 ≤ M ≤ 200.000)
- M dòng tiếp theo: mỗi dòng gồm hai số nguyên a và b thể hiện một tour du lịch tham quan các cây cầu đi từ đảo a đến đảo b.

Dữ liệu xuất:

- Một số nguyên duy nhất thể hiện số cây cầu chưa được tham quan.

Ví dụ

  • input
    6
    1 2
    2 3
    2 4
    4 5
    4 6
    2
    3 6
    5 6
    output
    1
Back to Top