維持排序的鄰接表圖

題目敘述

請實作一個無向圖的資料結構，頂點編號為 1 到 n，每個頂點用一份鄰居清單記錄與它相連的頂點。這份清單要隨時保持由小到大排序：每加入一條邊，查詢結果就必須立刻正確，不能等全部加完再一次排序。後面的 BFS、DFS 題目都靠這個固定順序走訪鄰居。

同一對頂點之間重複的邊只算一條，連到自己的邊（u = v）要忽略。

函式介面

請繳交 graph.h 與 graph.c，並實作下列介面：

typedef struct graph graph;

void graph_init(graph *g, int n);
void graph_add_edge(graph *g, int u, int v); /* undirected; ignore duplicate edges */
int graph_degree(graph *g, int u); /* number of neighbors of u */
int graph_neighbor(graph *g, int u, int i); /* i-th neighbor (0-indexed), sorted ascending */
int graph_edge_count(graph *g); /* distinct undirected edges stored */

輸入格式

評測用的主程式依序讀入：

• 第 1 行：整數 n 與 m。
• 接下來 m 行：每行兩個整數 u 與 v，表示一條無向邊。
• 下一行：整數 Q，接著 Q 行查詢。

查詢有三種：

• deg u：頂點 u 的鄰居數。
• neighbor u i：頂點 u 由小到大排序後的第 i 個鄰居（i 從 0 開始）。
• edges：目前不同的無向邊總數。

輸出格式

每個查詢輸出一行，內容為該查詢的答案。

限制

• 壓力測試中 1 ≤ n ≤ 500。
• 大型稀疏測試中 0 ≤ m ≤ n。
• 每個頂點的鄰居必須嚴格遞增儲存。

範例

範例 1

輸入

4 3
1 2
1 3
2 4
5
deg 1
neighbor 1 0
neighbor 1 1
edges
deg 4

輸出

2
2
3
3
1

範例 2

輸入

3 3
1 2
1 2
1 1
2
edges
deg 1

輸出

1
1

範例 3

輸入

1 0
2
deg 1
edges

輸出

0
0

範例 4

輸入

3 2
1 3
1 2
3
neighbor 1 0
neighbor 1 1
edges

輸出

2
3
2

範例 5

輸入

3 2
1 2
2 3
4
deg 2
neighbor 2 0
edges
neighbor 1 0

輸出

2
1
2
2

說明

• 兩個端點要互相記錄：加入 u → v 時，v 要放進 u 的清單，u 也要放進 v 的清單。
• 重複的邊與自環都不能改變任何頂點的度數，也不能算進 edges 的結果。
• edges 回答的是「不同的邊」有幾條，不是 graph_add_edge 被呼叫了幾次。
• 範例 1：頂點 1 的鄰居是 2 與 3，所以度數為 2；整張圖共 3 條邊；頂點 4 只連到 2。
• 範例 2：第二條 1 2 是重複的邊，1 1 是自環，兩者都被忽略，所以只剩一條邊，頂點 1 的度數為 1。
• 範例 3：只有一個孤立頂點，度數與邊數都是 0。
• 範例 4：邊是先加 1 3 再加 1 2，但頂點 1 的第 0 個鄰居仍然是 2，第 1 個是 3。