Tâm rất yêu thích lập trình tạo phần mềm. Vào dịp rảnh rỗi Tâm đã thiết kế một phần mềm đơn giản. Màn hình phần mềm gồm $N$ địa điểm (đánh số từ $1$ đến $N$), trong đó mỗi địa điểm có đặt một bóng đèn ở trạng thái sáng hoặc tắt. Có $N-1$ con đường một chiều nối trực tiếp giữa các cặp điểm. Mỗi lần Tâm chạm tay vào một địa điểm $X_i$ bất kỳ trên màn hình thì sẽ có một robot xuất phát từ địa điểm $X_i$ di chuyển theo các con đường một chiều, cuối cùng kết thúc ở địa điểm $1$. Robot không thay đổi trạng thái đèn ở địa điểm $X_i$ và địa điểm $1$, các địa điểm còn lại robot đã đi qua thì đèn ở địa điểm đó sẽ thay đổi sang trạng thái ngược lại (sáng thành tắt, tắt thành sáng)

Yêu cầu: Hãy cho biết khi Tâm thực hiện $K$ lần chạm tay (mỗi lần chạm tay vào một địa điểm) thì sau đó sẽ có bao nhiêu địa điểm có đèn sáng. Biết rằng robot xuất phát từ địa điểm bất kỳ luôn có thể di chuyển theo các con đường một chiều đến địa điểm $1$

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

3

4 1
0 0 0 0
3 1
2 3
4 2
4

2