Tí là người nghiện nước ngọt hãng P, người yêu có thể không có, nhưng nước ngọt hãng P thì phải có ít nhất ~2~ lon mỗi ngày. Tí được chẩn đoán nếu tiếp tục thói quen này, Tí vừa suy giảm sức khỏe vừa không thể có người yêu nên Tí quyết định cai nghiện. Nhưng một khi đã nghiện thì khó thoát, Tí vẫn luôn mơ thấy những lon nước sủi bọt gas ngọt ngào ấy và những hòn đảo kì lạ.

Trong mơ, Tí biết được rằng có ~N~ hòn đảo và ~M~ cây cầu có sẵn. Những lon nước ngọt sẽ nằm trên những cây cầu thuộc đường đi đơn giữa ~2~ hòn đảo bất kì dài nhất, hay nói cách khác, số lon nước ngọt bằng độ dài đường đi đơn giữa ~2~ đỉnh bất kì dài nhất. Biết rằng đường đi đơn giữa ~2~ hòn đảo có độ dài ~k~ dạng ~a_1, a_2, ... a_k, a_{k+1}~, trong đó ~a_1, a_2, ... a_k, a_{k+1}~ là những hòn đảo đôi một khác nhau và có cây cầu nối trực tiếp giữa hòn đảo ~a_i~ và ~a_{i+1}~ với ~1 \le i \le k~. Một nhóm các hòn đảo là tập hợp những hòn đảo có thể đi đến nhau thông qua những cây cầu. Điều đặc biệt giữa những hòn đảo này chính là chỉ tồn tại nhiều nhất một đường đi đơn giữa hai hòn đảo bất kỳ.

Bên cạnh đó, Tí còn được ban cho ~2~ loại phép thuật:

• Phép thuật thứ nhất có dạng ~1~ ~a~ ~b~ cho phép Tí xây dựng một cây cầu nối giữa ~1~ đỉnh bất kì thuộc nhóm chứa hòn đảo ~a~ và ~1~ đỉnh bất kì thuộc nhóm chứa hòn đảo ~b~. Tuy nhiên, phép thuật này đã bị mẹ của Tí ngăn cản một phần vì mẹ không thích Tí uống quá nhiều nước ngọt kể cả trong mơ. Nên Tí chỉ có thể nối sao cho đường đi đơn dài nhất sau khi nối là ngắn nhất có thể. Nếu ~a~ và ~b~ đã cùng một nhóm trước đó thì không có gì xảy ra.
• Phép thuật thứ hai có dạng ~2~ ~k~ cho phép Tí biết được đường đi đơn dài nhất thuộc nhóm chứa hòn đảo ~k~ để ước lượng khả năng uống của mình.

Yêu cầu: Tí thực hiện lần lượt ~Q~ lần phép thuật. Với mỗi phép thuật loại thứ hai, bạn hãy giúp Tí đếm xem Tí sẽ được uống bao nhiêu lon nhé.

Dữ liệu vào

• Dòng đầu tiên chứa ~3~ số nguyên ~N, M, Q~ ~(1 \le N, Q \le 2 * 10^5, 0 \le M \le N - 1)~ lần lượt là số hòn đảo, số cây cầu có sẵn và số lần thực hiện phép thuật.
• ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u, v~ ~(1 \le u, v \le N)~ cho biết có một cây cầu nối sẵn giữa ~2~ hòn đảo ~u~ và ~v~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một loại phép thuật trong ~2~ loại:
  • ~1~ ~a~ ~b~ ~(1 \le a,b \le N)~
  • ~2~ ~k~ ~(1 \le k \le N)~

Dữ liệu ra

Với mỗi phép thuật loại thứ hai, bạn hãy in ra số lon nước ngọt thuộc nhóm chứa hòn đảo ~k~.

Ví dụ

Đầu vào

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

Đầu ra

2

Giải thích

• Ban đầu, khi chưa thực hiện phép thuật nào:

  

• Sau khi thực hiện lần lượt ~4~ lần phép thuật thứ nhất:

  

• Cuối cùng, Tí thực hiện phép thuật thứ hai, nhóm chứa hòn đảo ~3~ có độ dài đường đi đơn dài nhất là ~2~ nên Tí sẽ được uống ~2~ lon nước ngọt ở nhóm hòn đảo này.

Tính điểm

• Subtask ~1~ (30% số điểm): ~1 \le N, Q \le 1000~
• Subtask ~2~ (70% số điểm): Không có ràng buộc gì thêm.