Bipartite Graph

시간 제한2초메모리 제한1024 MB

요약

각 d에 대해 왼쪽 d개, 오른쪽 d-2개의 꼭짓점을 가진 이분 그래프를 만들되, 간선이 3d개 이하이고 왼쪽 꼭짓점 두 개를 어떤 식으로 지워도 완전 매칭이 남아야 한다.

난이도: 보통10점 중 7점
유형: 그래프, 그리디
정답자: 아직 제출이 없습니다

문제

In this problem, you have to construct a bipartite graph which has the following properties:

The number of vertices in the first part is $d$ .
The number of vertices in the second part is $d - 2$ .
The number of edges is at most $3 d$ .
For all bipartite graphs constructed by removing two vertices from the first part, there is a perfect matching.

Recall that a bipartite graph is a graph where the vertices are divided into two parts so that each edge connects a vertex from the first part and a vertex from the second part. A perfect matching is a collection of edges such that each vertex of the graph is an end of exactly one edge from that collection.

입력

The first line contains an integer $T$ , the number of test cases ( $1 \le T \le 100$ ). Each of the next $T$ lines contains an integer $d$ , the number of vertices in the corresponding test case ( $3 \le d \le 100$ ).

출력

For each test case, start by printing an integer $m$ , the number of edges, on a separate line. On the next $m$ lines, print the edge descriptions. Each edge description is a pair of integers $u$ and $v$ : the numbers of vertices of the first and the second part connected by that edge ( $0 \le u < d$ , $0 \le v < d - 2$ ).

The graph must not contain multiple edges.

힌트

You do not need to minimize the number of edges.

예제1

예제 1
입력
```
1
4
```
예상 출력
```
7
0 1
1 0
1 1
2 0
2 1
3 0
3 1
```