Chơi lửa chùa (D div 1)

Xem PDF

Điểm: 300 Thời gian: 1.75s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hôm nay WuTan đang chơi game "Lửa chùa" với những người bạn của mình.

"Lửa chùa" là một tựa game chiến thuật, tư duy, sinh tồn đỉnh cao, không phân biệt cày chay và nạp vip, nơi mà những người bạn có những thời gian vui vẻ với nhau. Vì thấy tựa game này rất hay nên WuTan chơi suốt ngày, quên ăn quên ngủ. Lần này WuTan đang trải nghiệm chế độ mới của tựa game mang tên "Sơn tăng dame". Cụ thể trong chế độ này sẽ có \(n\) ngôi nhà được đánh số từ \(1\) đến \(n\), có \(n-1\) đường đi hai chiều nối \(2\) ngôi nhà với nhau ( đảm bảo tạo thành cây ), trong đó sẽ có \(m\) ngôi nhà đặc biệt được sơn. Để chiến thắng thì người chơi cần xóa một số ngôi nhà không được sơn ( không được xóa nhà được sơn ) sao cho không có \(2\) ngôi nhà được sơn nào có thể đi đến với nhau.

Bây giờ WuTan phân vân không biết phải xóa ít nhất bao nhiêu ngôi nhà không được sơn để có thể chiến thắng, hãy giúp cậu ấy nhé !

Input

  • Dòng đầu tiên là hai số nguyên dương \(n,m\).
  • \(n-1\) dòng tiếp theo mỗi dòng là \(2\) số \(u,v\) biểu thị có đường đi nối \(2\) ngôi nhà này.
  • Dòng cuối cùng là dãy \(C_1,C_2,...,C_m\) biểu thị các ngôi nhà được sơn.

Output

  • Gồm một số nguyên duy nhất là kết quả, nếu không tồn tại cách xóa thỏa mãn thì in ra \(-1\).

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(m \le n \le 20\)
  • Subtask \(2\) (\(20\%\) số điểm): \(m \le n \le 1000\)
  • Subtask \(3\) (\(60\%\) số điểm): \(m \le n \le 5*10^5\)

Example

Test 1

Input
10 4
1 3
1 6
5 10
3 5
5 9
6 7
8 6
2 4
4 6
1 2 9 10
Output
2
Note

Giải thích: Xóa các ngôi nhà \(4,5\).


Bình luận


  • 0
    a52027duonghn    8:30 p.m. 7 Tháng 8, 2022

    fai fai đồng đội em :))


    • 0
      phubinh2k10    5:26 p.m. 7 Tháng 8, 2021

      "Sơn tăng dame"
      :v


      • 0
        minh47587    6:05 p.m. 8 Tháng 7, 2021

        burh :))


        • 6
          deptrai2k7    6:52 p.m. 2 Tháng 7, 2021 chỉnh sửa 4

          Small.Thưa thầy là em muốn đóng góp thêm test được không ạ? Em thấy "một số" code có thể chết test này nhưng hình như trong bộ test của mình không có. Em cám ơn thầy!!

          2 phản hồi

          • 3
            Lê_Gia_Khánh    11:53 a.m. 1 Tháng 7, 2021

            Khi nào có sol, em mong là có prove luôn cho em hiểu :((