{"code":"dinhcanke","name":"Đỉnh cận kề","description":"Cho đồ thị $N$ đỉnh ban đầu có $M$ cạnh hai chiều, thực hiện $Q$ truy vấn trong hai loại sau:\r\n\r\n- **+ $u$ $v$**: thêm cạnh giữa hai đỉnh $u$ và $v$\r\n- **? $u$ $v$**: hỏi hai đỉnh $u$ và $v$ có cận kề với nhau không, hai đỉnh gọi là cận kề nếu tồn tại một đỉnh $w$ mà có cạnh $(u, w)$ và $(w, v)$.\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa số $N, M, Q$ ($1\\le N, M, Q \\le 10^5$)\r\n\r\n- $M$ dòng tiếp theo mỗi dòng chứa hai số $u, v$ mô tả các cạnh ban đầu của đồ thị \r\n\r\n- $Q$ dòng tiếp theo mô tả các truy vấn.\r\n\r\n

Output

\r\n\r\n- Đưa ra xâu 01 mô tả kết quả của truy vấn loại \"?\", 0 là không cận kề, 1 là ngược lại.\r\n\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 8 9 9\r\n 5 8\r\n 3 1\r\n 4 8\r\n 7 5\r\n 6 2\r\n 4 3\r\n 2 3\r\n 6 1\r\n 3 8\r\n ? 6 2\r\n + 1 2\r\n ? 6 2\r\n ? 5 4\r\n ? 6 4\r\n + 8 6\r\n ? 6 4\r\n ? 4 8\r\n ? 5 2\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 0110110\r\n ```","points":400.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}