VM 13 Bài 22 - Dãy đèn năm xưa

View as PDF

Submit solution

Points: 1.18 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VM13 - Lê Khắc Minh Tuệ
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

"You're half a world away" - 3/11/2011 Miss you

Hai năm trước, cô bé Tôm tinh nghịch được bạn mình tặng cho một món đồ chơi nhân ngày sinh nhật.

Món đồ chơi là một nhóm rất nhiều bóng đèn. Các bóng đèn được nối với nhau bằng những sợi dây điện. Mỗi bóng đèn có một công tắc. Khi bấm vào công tắc, trạng thái bật tắt của bóng đèn sẽ thay đổi.

Hai năm trôi qua, người bạn tặng món quà đó cho Tôm đã đi du học. Nhưng những gì ẩn chứa trong món đồ chơi đó dường như vẫn là một bí mật quá lớn. Tôm đã mất nhiều công sức để tìm tòi, đặt ra những thử thách cho riêng mình để có thể khám phá trọn vẹn được món đồ chơi.

Người bạn của Tôm có rất nhiều điều muốn chia sẻ. Vậy nhưng người ấy luôn ngại ngùng, ~e~ thẹn, nên đành dấu những lời thầm kín vào trong một bức thư. Để đọc hiểu được bức thư ấy, Tôm cần phải thao tác trên món đồ chơi bằng những lệnh mà bức thư chỉ ra.

Bức thư có rất nhiều lệnh. Mỗi lệnh thuộc một trong hai loại:

  • Loại thứ nhất có dạng "switch ~i~": Tôm sẽ phải bấm vào công tắc ~i~. Khi bấm vào công tắc ~i~, trạng thái bật tắt của bóng đèn ~i~ sẽ thay đổi.
  • Loại thứ hai có dạng "print ~s_1~ ~s_2~", trong đó ~s_1~, ~s_2~ nhận một trong hai giá trị ~0~ hoặc ~1~, ~0~ tượng trưng cho 'tắt', ~1~ tượng trưng cho 'bật': Tôm cần đếm xem có bao nhiêu sợi dây điện đang nối hai bóng đèn ~u~, ~v~ mà trạng thái bật tắt hiện tại của ~u~ là ~s_1~, trạng thái bật tắt hiện tại của ~v~ là ~s_2~.

Đầu bức thư, người bạn của Tôm viết cho Tôm trạng thái bật tắt ban đầu của các bóng đèn. Để hiểu được người bạn ấy muốn nhắn nhủ điều gì, Tôm chỉ phải thực hiện lần lượt các lệnh ở trong bức thư.

Tuy nhiên, do người bạn của Tôm quên mất rằng Tôm không phải lập trình viên, nên đã gửi một bức thư với rất nhiều lệnh. Tôm cần các thí sinh VM giúp đỡ. Các bạn hãy giúp cô bé đáng yêu này nhé!

Input

  • Dòng đầu tiên là số ~n~, ~m~, là số lượng bóng đèn và số lượng dây điện. Các bóng đèn được đánh số từ ~1~ đến ~n~. ~m~ có giá trị không vượt quá ~\frac{n \times (n-1)}{2}~.

  • ~m~ dòng sau, mỗi dòng gồm hai số nguyên ~x_{i}~ và ~y_{i}~, thể hiện dây điện thứ ~i~ nối hai bóng đèn ~x_{i}~ và ~y_{i}~. Không có ~2~ sợi dây nào nối cùng ~2~ bóng đèn. Không có sợi dây nào nối một bóng đèn với chính nó.

  • Dòng tiếp theo chứa ~n~ số nguyên ~0~ hoặc ~1~. Số nguyên thứ ~i~ thể hiện trạng thái bật tắt ban đầu của bóng đèn thứ ~i~. ~0~ thể hiện bóng đèn ~i~ đang tắt, ~1~ thể hiện bóng đèn ~i~ đang bật.

  • Dòng tiếp theo là số ~q~, là số lượng lệnh trong bức thư.

  • ~q~ dòng tiếp theo, mỗi dòng miệu tả một dòng của bức thư. Có hai dạng lệnh:

    • "switch ~i~" ~(1 \leq i \leq n)~: Thay đổi trạng thái bật tắt của bóng đèn ~i~.
    • "print ~s_1~ ~s_2~" ~(s_1~, ~s_2~ nhận giá trị ~0~ hoặc ~1)~: Cần in ra số lượng dây điện đang nối các bóng đèn có trạng thái bật tắt là ~s_1~ s2.

Output

  • Với mỗi lệnh dạng print, cần in ra trên một dòng kết quả của lệnh đó.

Giới hạn

  • ~1 \leq n~, ~m~, ~q \leq 100~, ~000~;
  • Có ~20\%~ số test có ~n \leq 100~, ~q \leq 10~, ~000~.

Sample Input

5 7
1 5
1 3
2 4
2 5
3 4
3 5
4 5
0 0 0 0 0
8
print 0 0
switch 1
print 0 1
switch 5
switch 3
print 1 1
print 1 0
print 0 0

Sample Output

7
2
3
3
1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.