Động đất

View as PDF

Submit solution


Points: 0.32 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
USACO January 2009 - Gold DivisionTranslated by duyhung123abc
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một trận động đất vừa xảy ra ở Wisconsin và tàn phá trang trại của nông dân John. Trận động đất đã phá hủy một số cánh đồng khiến cho đàn bò không thể đặt chân lên cánh đồng đó. Một điều khác thường là tất cả con đường nối các cánh đồng đều không bị tàn phá.

Như thường lệ, trang trại được xem là một tập hợp các ~P~ cánh đồng ~(1 \le P \le 30000)~ được đánh số từ ~1~ đến ~P~ và được nối với nhau bằng ~C~ đường đi hai chiều ~(1 \le C \le 100000)~ đánh số từ ~1~ đến ~C~. Đường đi thứ ~i~ nối hai cánh đồng ~a_i~ và ~b_i~ ~(1 \le~ ~a_i~ ~b_i~ ~\le P)~. Chú ý là các đường đi có thể nối cánh đồng ~a_i~ với chính nó hoặc giữa ~2~ cánh đồng có thể có nhiều đường đi. Chuồng bò được đặt ở cánh đồng ~1~.

Có ~N~ con bò ~(1 \le N \le P)~ ở các cánh đồng khác nhau gọi về cho FJ và thông báo ~1~ số nguyên ~report_j~ ~(2 \le~ ~report_j~ ~\le P)~ có nghĩa là cánh đồng ~report_j~ thỏa ~2~ điều kiện:

  • Cánh đồng ~report_j~ không bị tàn phá.
  • Con bò đứng ở cánh đồng ~report_j~ không thể về được cánh đồng ~1~ vì trên đường đi có một số cánh đồng bị tàn phá và không thể đi qua các cánh đồng đó

Cho biết thông tin của ~N~ con bò, hãy xác định số lượng ít nhất các cánh đồng sao cho từ các cánh đồng đó không thể về được cánh đồng ~1~ (bao gồm luôn những cánh đồng bị phá hủy)

Input

  • Dòng đầu chứa 3 số nguyên: ~P~, ~C~ và ~N~
  • ~C~ dòng sau mỗi dòng chứa ~2~ số ~a_i~ và ~b_i~ mô tả đường nối thứ ~i~ nối hai cánh đồng ~a_i~ và ~b_i~
  • ~N~ dòng sau mỗi dòng chứa một số nguyên là thông tin của các con bò

Output

Gồm ~1~ dòng duy nhất là số lượng ít nhất các cánh đồng không về được cánh đồng ~1~.

Sample Input

4 3 1
1 2
2 3
3 4
3

Sample Output

3

Note

Cánh đồng ~2~ bị phá hủy, vậy các con bò ở cánh đồng ~2~, ~3~, ~4~ sẽ không thể về chuồng


Comments

Please read the guidelines before commenting.