Three-Axis Views

source: International Collegiate Programming Contest, Asia Regional 2020, Japan

raw_problem:
Three-Axis Views

A friend of yours is an artist designing Image-Containing Projection Cubes (ICPCs). An ICPC
is a crystal cube with its side of integer length. Some of its regions are made opaque through
an elaborate laser machining process. Each of the opaque regions is a cube of unit size aligned
with integer coordinates.

Figure A.1 depicts an ICPC as given in the Sample Input 1. Here, the green wires correspond
to the edges of the crystal cube. The blue small cubes correspond to the cubic opaque regions
inside the crystal.

  Figure A.1. ICPC of Sample Input 1

  ICPCs are meant to enjoy the silhouettes of its opaque regions projected by three parallel lights perpendicular to its faces. Figure A.2 depicts the ICPC and its three silhouettes.

Figure A.2. ICPC of Sample Input 1 and its silhouettes (dashed-dotted lines are the
edges of the parallel light perpendicular to the left face)

Your job is to write a program that decides whether there exists an ICPC that makes the given
silhouettes.

Input

  The input consists of a single test case of the following format.

$n$
$s_1$
...
$s_n$
$t_1$
...
$t_n$
$u_1$
...
$u_n$

  Here, $n$ is the size of the ICPC, an integer between 1 and 100, inclusive.

  The ICPC of size $n$ makes three silhouettes of $n \times n$ squares of dark and bright cells. Cells are dark if they are covered by the shadows of opaque unit cubes, and are bright, otherwise. The $3n$ lines, each with $n$ digits, starting from the second line of the input denote the three silhouettes of the ICPC, where '0' represents a bright cell and '1' represents a dark cell. At least one of the digits in the $3n$ lines is '1'.

  First comes the data for the silhouette on the $yz$-plane, where the first line $s_1$ gives the cells of the silhouettes with the largest $z$-coordinate value. They are in the order of their $y$-coordinates. The following lines, $s_2,..., s_n$, give the cells with the decreasing values of their $z$-coordinates.

  Then comes the data for the silhouette on the $zx$-plane, where the first line, $t_1$ gives the cells with the largest $x$-coordinate value, in the order of their $z$-coordinates. The following lines, $t_2, ..., t_n$, give the cells with the decreasing values of their $x$-coordinates.

  Finally comes the data for the silhouette on the $xy$-plane, where the first line, $u_1$, gives the cells with the largest $y$-coordinate value, in the order of their $x$-coordinates. The following lines, $u_2, ...,  u_n$, give the cells with the decreasing values of their $y$-coordinates.

  The following figure depicts the three silhouettes of the ICPC given in the Sample Input 1.

Figure A.3. 0-1 representations of silhouettes (Sample Input 1)

Output

  Print "Yes" if it is possible to make an ICPC with the given silhouettes. Print "No", otherwise.

Sample Input 1

3
010
010
111
100
111
101
011
111
010

Sample Output 1

Yes

Sample Input 2

2
00
01
00
10
10
00

 Sample Output 2

Yes

Sample Input 3

2
00
00
00
10
10
00

 Sample Output 3

No

Sample Input 4

2
01
00
00
10
10
00

 Sample Output 4

No

solutions: ["n = int(input())\nS = [list(map(int, input())) for _ in range(n)]\nT = [list(map(int, input())) for _ in range(n)]\nU = [list(map(int, input())) for _ in range(n)]\n\nTable = [[[1 for _ in range(n)] for _ in range(n)] for _ in range(n)]\nfor i in range(n):\n    for j in range(n):\n        if S[i][j] == 0:\n            for k in range(n):\n                Table[i][k][j] = 0\nfor i in range(n):\n    for j in range(n):\n        if T[j][n - 1 - i] == 0:\n            for k in range(n):\n                Table[i][n - 1 - j][k] = 0\nfor i in range(n):\n    for j in range(n):\n        if U[i][j] == 0:\n            for k in range(n):\n                Table[k][j][n - 1 - i] = 0\n\nfor i in range(n):\n    for j in range(n):\n        if S[i][j] == 1:\n            flag = 0\n            for k in range(n):\n                flag |= Table[i][k][j]\n            if flag == 0:\n                print(\"No\")\n                exit()\n        if T[j][n - 1 - i] == 1:\n            flag = 0\n            for k in range(n):\n                flag |= Table[i][n - 1 - j][k]\n            if flag == 0:\n                print(\"No\")\n                exit()\n        if U[i][j] == 1:\n            flag = 0\n            for k in range(n):\n                flag |= Table[k][j][n - 1 - i]\n            if flag == 0:\n                print(\"No\")\n                exit()\nprint(\"Yes\")\n\n", "n = int(input())\n\ns = [list(map(int,input())) for _ in range(n)]\n\nt = [list(map(int,input())) for _ in range(n)]\n\nu = [list(map(int,input())) for _ in range(n)]\n\ntable = [[[1]*n for _ in range(n)]for _ in range(n)]\n\nfor i in range(n):\n    for j in range(n):\n        if(s[i][j]==0):\n            for k in range(n):\n                table[i][k][j]=0\n\n# for i in range(n):\n#     print(*table[i],sep=\"\\n\")\n#     print()\n\nfor i in range(n):\n    for j in range(n):\n        if(t[j][n-1-i]==0):\n            for k in range(n):\n                table[i][n-1-j][k]=0\n\n# for i in range(n):\n#     print(*table[i],sep=\"\\n\")\n#     print()\n\nfor i in range(n):\n    for j in range(n):\n        if(u[i][j]==0):\n            for k in range(n):\n                table[k][j][n-1-i]=0\n\n# for i in range(n):\n#     print(*table[i],sep=\"\\n\")\n#     print()\n#################################################\n\nfor i in range(n):\n    for j in range(n):\n        if(s[i][j]==1):\n            flg = 0\n            for k in range(n):\n                flg|=table[i][k][j]\n            if(not flg):\n                print(\"No\")\n                exit()\n\nfor i in range(n):\n    for j in range(n):\n        if(t[j][n-1-i]==1):\n            flg = 0\n            for k in range(n):\n                flg|=table[i][n-1-j][k]\n            if(not flg):\n                print(\"No\")\n                exit()\n\nfor i in range(n):\n    for j in range(n):\n        if(u[i][j]==1):\n            flg = 0\n            for k in range(n):\n                flg|=table[k][j][n-1-i]\n            if(not flg):\n                print(\"No\")\n                exit()\n\nprint(\"Yes\")\n"]

source: aizu

question:
Three-Axis Views

A friend of yours is an artist designing Image-Containing Projection Cubes (ICPCs). An ICPC
is a crystal cube with its side of integer length. Some of its regions are made opaque through
an elaborate laser machining process. Each of the opaque regions is a cube of unit size aligned
with integer coordinates.

Figure A.1 depicts an ICPC as given in the Sample Input 1. Here, the green wires correspond
to the edges of the crystal cube. The blue small cubes correspond to the cubic opaque regions
inside the crystal.

![image](1.png)

  Figure A.1. ICPC of Sample Input 1

  ICPCs are meant to enjoy the silhouettes of its opaque regions projected by three parallel lights perpendicular to its faces. Figure A.2 depicts the ICPC and its three silhouettes.

![image](2.png)
Figure A.2. ICPC of Sample Input 1 and its silhouettes (dashed-dotted lines are the
edges of the parallel light perpendicular to the left face)

Your job is to write a program that decides whether there exists an ICPC that makes the given
silhouettes.

Input

  The input consists of a single test case of the following format.

$n$
$s_1$
...
$s_n$
$t_1$
...
$t_n$
$u_1$
...
$u_n$

  Here, $n$ is the size of the ICPC, an integer between 1 and 100, inclusive.

  The ICPC of size $n$ makes three silhouettes of $n \times n$ squares of dark and bright cells. Cells are dark if they are covered by the shadows of opaque unit cubes, and are bright, otherwise. The $3n$ lines, each with $n$ digits, starting from the second line of the input denote the three silhouettes of the ICPC, where '0' represents a bright cell and '1' represents a dark cell. At least one of the digits in the $3n$ lines is '1'.

  First comes the data for the silhouette on the $yz$-plane, where the first line $s_1$ gives the cells of the silhouettes with the largest $z$-coordinate value. They are in the order of their $y$-coordinates. The following lines, $s_2,..., s_n$, give the cells with the decreasing values of their $z$-coordinates.

  Then comes the data for the silhouette on the $zx$-plane, where the first line, $t_1$ gives the cells with the largest $x$-coordinate value, in the order of their $z$-coordinates. The following lines, $t_2, ..., t_n$, give the cells with the decreasing values of their $x$-coordinates.

  Finally comes the data for the silhouette on the $xy$-plane, where the first line, $u_1$, gives the cells with the largest $y$-coordinate value, in the order of their $x$-coordinates. The following lines, $u_2, ...,  u_n$, give the cells with the decreasing values of their $y$-coordinates.

  The following figure depicts the three silhouettes of the ICPC given in the Sample Input 1.

![image](3.png)

Figure A.3. 0-1 representations of silhouettes (Sample Input 1)

Output

  Print "Yes" if it is possible to make an ICPC with the given silhouettes. Print "No", otherwise.

Sample Input 1

3
010
010
111
100
111
101
011
111
010

Sample Output 1

Yes

Sample Input 2

2
00
01
00
10
10
00

 Sample Output 2

Yes

Sample Input 3

2
00
00
00
10
10
00

 Sample Output 3

No

Sample Input 4

2
01
00
00
10
10
00

 Sample Output 4

No

image_tags:
3D Geometry
3D Geometry
3D Geometry

data_split: test


CODE FESTIVAL 2016 Final - Reverse Grid

input_output: {"inputs": ["1 12\nctdefesoival", "0 12\nctdefesoival", "2 2\ncf\ndf", "2 2\ncf\nde", "0 12\nctdffesoival", "0 1\nctdffesoival", "0 1\ncfdftesoival", "0 2\ncfdftesoival", "0 4\ncfdftesoival", "0 2\ncfdftetoival", "0 4\ncfdftetoival", "2 0\ncf\ncf", "1 7\ncodefestival", "1 12\nlaviosefedtc", "0 12\nlaviosefedtc", "0 17\nctdffesoival", "0 1\nbtdffesoival", "0 0\ncfdftesoival", "0 7\ncfdftesoival", "0 2\nlaviotetfdfc", "0 4\ncfcftetoival", "2 0\nfc\ncf", "1 7\nlavitsefedoc", "1 12\nlavjosefedtc", "0 12\nlavioeefsdtc", "0 29\nctdffesoival", "0 2\nbtdffesoival", "0 0\nbfdftesoival", "0 4\nlaviotetfcfc", "2 1\nfc\ncf", "1 7\nlavitscfedoe", "1 10\nlavjosefedtc", "0 24\nlavioeefsdtc", "0 55\nctdffesoival", "1 2\nbtdffesoival", "0 0\nbfdetesoival", "0 4\ncfcftetoiv`l", "1 7\nlavittcfedoe", "0 10\nlavjosefedtc", "0 24\nlavifeeosdtc", "0 55\ndtdffesoival", "0 3\nbtdffesoival", "0 0\nbfdetdsoival", "1 4\ncfcftetoiv`l", "1 7\nlavittbfedoe", "0 10\nlavjosdfedtc", "0 24\nl`vifeeosdtc", "0 55\ndudffesoival", "0 3\nbtdfaesoivfl", "0 0\nbfdetdslivao", "1 4\nl`viotetfcfc", "0 7\nlavittbfedoe", "0 24\nl`vjfeeosdtc", "0 45\ndudffesoival", "0 3\nbtdfaesfivol", "0 0\noavilsdtedfb", "0 0\ncfcftetoiv`l", "0 2\nlavittbfedoe", "1 24\nl`vjfeeosdtc", "0 45\ndudafesoivfl", "1 0\noavilsdtedfb", "0 0\ncfcftetoiw`l", "0 2\nlbvittbfedoe", "1 24\nl`vjgeeosdtc", "0 45\ndudafespivfl", "2 0\noavilsdtedfb", "1 0\ncfcftetoiw`l", "0 0\nlbvittbfedoe", "1 37\nl`vjfeeosdtc", "0 43\ndudafespivfl", "1 0\noavilsdtedeb", "1 0\ncfcetetoiw`l", "0 0\neodefbttivbl", "1 37\nctdsoeefjv`l", "0 33\ndudafespivfl", "0 0\noavilsdtedeb", "1 0\ncecftetoiw`l", "1 0\neodefbttivbl", "0 37\nctdsoeefjv`l", "0 33\ncudafespivfl", "0 0\nbedetdslivao", "2 0\ncecftetoiw`l", "1 0\nlbvittbfedoe", "0 39\nctdsoeefjv`l", "0 19\ncudafespivfl", "2 0\ncecft`toiwel", "1 0\nlbvittbfedof", "1 39\nctdsoeefjv`l", "0 19\ncusafedpivfl", "3 0\ncecft`toiwel", "2 0\nlbvittbfedof", "0 39\nl`vjfeeosdtc", "0 19\nlfvipdefasuc", "1 0\ncecft`toiwel", "2 1\nlbvittbfedof", "0 39\nl`vjfeeosctc", "1 0\ncecfu`toiwel", "2 1\nlbvjttbfedof", "1 1\ncecfu`toiwel", "3 1\nlbvjttbfedof", "2 2\ncf\ncf", "1 12\ncodefestival"], "outputs": ["2\n", "1\n", "12\n", "24\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "2\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "2\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "2\n", "2\n", "1\n", "1\n", "2\n", "1\n", "1\n", "2\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "2\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "1\n", "1\n", "1\n", "1\n", "2\n", "1\n", "1\n", "1\n", "1\n", "2\n", "1\n", "1\n", "1\n", "1\n", "2\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "1\n", "1\n", "1\n", "1\n", "1\n", "1\n", "2\n", "1\n", "1\n", "2\n", "1\n", "2\n", "6", "2"]}

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>1900</var> 点

問題文

縦 <var>H</var> 行、横 <var>W</var> 列のマス目があり、<var>i</var> 行目の <var>j</var> 列目のマスには文字 <var>S_{i,j}</var> が書かれています。

すぬけくんはこのマス目に対して以下の <var>2</var> 種類の操作を行うことが出来ます。

行リバース：行を <var>1</var> つ選び、その行をリバースする。

列リバース：列を <var>1</var> つ選び、その列をリバースする。

例えば、<var>2</var> 行目をリバースした後に <var>4</var> 列目をリバースすると以下のように変化します。

上記の操作を好きな順番で何回か行うことによって作ることの出来る文字の配置は何通り考えられるでしょうか？

制約

<var>1≦H,W≦200</var>

<var>S_{i,j}</var> は小文字アルファベット（a-z）である。

入力

入力は以下の形式で標準入力から与えられる。

<var>H</var> <var>W</var>
<var>S_{1,1}</var><var>S_{1,2}</var><var>...</var><var>S_{1,W}</var>
<var>S_{2,1}</var><var>S_{2,2}</var><var>...</var><var>S_{2,W}</var>
<var>:</var>
<var>S_{H,1}</var><var>S_{H,2}</var><var>...</var><var>S_{H,W}</var>

出力

答えを <var>1000000007 (=10^9+7)</var> で割ったあまりを出力せよ。

入力例 1

2 2
cf
cf

出力例 1

6

以下の <var>6</var> 通りの配置が考えられます。

入力例 2

1 12
codefestival

出力例 2

2

Score : <var>1900</var> points

Problem Statement

Snuke has a grid with <var>H</var> rows and <var>W</var> columns. The square at the <var>i</var>-th row and <var>j</var>-th column contains a character <var>S_{i,j}</var>.

He can perform the following two kinds of operation on the grid:

Row-reverse: Reverse the order of the squares in a selected row.

Column-reverse: Reverse the order of the squares in a selected column.

For example, reversing the <var>2</var>-nd row followed by reversing the <var>4</var>-th column will result as follows:

By performing these operations any number of times in any order, how many placements of characters on the grid can be obtained?

Constraints

<var>1≦H,W≦200</var>

<var>S_{i,j}</var> is a lowercase English letter (a-z).

Input

The input is given from Standard Input in the following format:

<var>H</var> <var>W</var>
<var>S_{1,1}</var><var>S_{1,2}</var><var>...</var><var>S_{1,W}</var>
<var>S_{2,1}</var><var>S_{2,2}</var><var>...</var><var>S_{2,W}</var>
<var>:</var>
<var>S_{H,1}</var><var>S_{H,2}</var><var>...</var><var>S_{H,W}</var>

Output

Print the number of placements of characters on the grid that can be obtained, modulo <var>1000000007 (=10^9+7)</var>.

Sample Input 1

2 2
cf
cf

Sample Output 1

6

The following <var>6</var> placements of characters can be obtained:

Sample Input 2

1 12
codefestival

Sample Output 2

2

question:
Snuke has a grid with $H$ rows and $W$ columns. The square at the $i$-th row and $j$-th column contains a character $S_{i,j}$.
He can perform the following two kinds of operation on the grid:

- Row-reverse: Reverse the order of the squares in a selected row.
- Column-reverse: Reverse the order of the squares in a selected column.

For example, reversing the $2$-nd row followed by reversing the $4$-th column will result as follows:
![image](1.png)
By performing these operations any number of times in any order, how many placements of characters on the grid can be obtained?

Constraints

- $1≦H,W≦200$
- $S_{i,j}$ is a lowercase English letter (a-z).

Input
The input is given from Standard Input in the following format:
$H$ $W$

$S_{1,1}$$S_{1,2}$$...$$S_{1,W}$

$S_{2,1}$$S_{2,2}$$...$$S_{2,W}$

$:$

$S_{H,1}$$S_{H,2}$$...$$S_{H,W}$

Output
Print the number of placements of characters on the grid that can be obtained, modulo $1000000007 (=10^9+7)$.

Sample Input 1
2 2
cf
cf

Sample Output 1
6

The following $6$ placements of characters can be obtained:
![image](2.png)

Sample Input 2
1 12
codefestival

Sample Output 2
2

image_tags: Patterns Patterns

data_split: test


Tile Setting

source: Kyoto University Programming Contest 2013

raw_problem:
J - タイル置き

サイズ<var>H</var>×<var>W</var>の盤面にサイズ1×2のタイルをマス目にそって<var>N</var>個配置する方法が何通りあるか求めたい.

タイルは重なってはいけない. また縦横どちらの向きに置いても構わない.

タイルは全て同じ見た目であり互いに区別しないものとする.

タイルは180度回転しても同じ見た目であり、区別しないものとする.

答えは大きくなる可能性があるので1,000,000,007で割った余りを答えよ

入力形式

入力は以下の形式で与えられる．

<var>H</var> <var>W</var> <var>N</var>

出力形式

タイルの置き方の総数を 1,000,000,007 で割った余りを出力せよ．

制約

<var>1 ≤ H ≤ 1,000,000,000</var>

<var>1 ≤ W ≤ 1,000,000,000</var>

<var>1 ≤ N ≤ 5</var>

入力値はすべて整数である．

この問題の判定には，50 点分のテストケースのグループが設定されている．このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす．

<var>1 ≤ H ≤ 6</var>

<var>1 ≤ W ≤ 6</var>

入出力例

入力例 1

2 2 1

出力例 1

4

次の4通りある。

入力例 2

2 2 2

出力例 2

2

次の2通りある

入力例 3

2 2 3

出力例 3

0

入力例 4

1000000000 1000000000 5

出力例 4

68450176

source: aizu

question:
J - Tile Placement

We want to find out how many ways there are to place $N$ tiles of size 1×2 on a board of size $H$×$W$, along the grids.
Tiles must not overlap. They can be placed either horizontally or vertically.
Tiles all have the same appearance and are indistinguishable from each other.
Tiles are also indistinguishable even when rotated 180 degrees.
Since the answer can be large, output the remainder when divided by 1,000,000,007.
Input format

The input is given in the following format.

$H$ $W$ $N$

Output format
Output the remainder of the total number of ways to place the tiles when divided by 1,000,000,007.

Constraints

- $1 ≤ H ≤ 1,000,000,000$
- $1 ≤ W ≤ 1,000,000,000$
- $1 ≤ N ≤ 5$
- All input values are integers.

For the judgement of this problem, a group of test cases worth 50 points has been set. In addition to the above constraints, the test cases included in this group also satisfy the following constraints.

- $1 ≤ H ≤ 6$
- $1 ≤ W ≤ 6$

Input/output examples
Input example 1

2 2 1

Output example 1

4

There are the following 4 ways.
![image](1.png)
Input example 2

2 2 2

Output example 2

2

There are the following 2 ways
![image](2.png)
Input example 3

2 2 3

Output example 3

0

Input example 4

1000000000 1000000000 5

Output example 4

68450176

image_tags:
2D Geometry
2D Geometry

data_split: test


solutions: ["def advice(agents, n):\n\tfrontier = {(x, y) for (x, y) in agents if 0 <= x < n and 0 <= y < n}\n\tbag = {(x, y) for x in range(n) for y in range(n)}\n\tif frontier == bag:\n\t\treturn []\n\twhile frontier and bag > frontier:\n\t\tbag -= frontier\n\t\tfrontier = {pos for (x, y) in frontier for pos in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)) if pos in bag}\n\treturn sorted(bag)\n", "def advice(agents, n):\n\tagents = [(a[0], a[1]) for a in agents if 0 <= a[0] < n and 0 <= a[1] < n]\n\tif len(agents) == n * n or n == 0:\n\t\treturn []\n\tgrid = [[0] * n for _ in range(n)]\n\tfor (ax, ay) in agents:\n\t\tgrid[ax][ay] = 1\n\tfor (ax, ay) in agents:\n\t\tfor (dx, dy) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:\n\t\t\t(nx, ny) = (ax + dx, ay + dy)\n\t\t\tif 0 <= nx < n and 0 <= ny < n and (grid[nx][ny] == 0):\n\t\t\t\tgrid[nx][ny] = grid[ax][ay] + 1\n\t\t\t\tagents.append((nx, ny))\n\tmax_dist = max((d for row in grid for d in row))\n\treturn [(x, y) for x in range(n) for y in range(n) if grid[x][y] == max_dist]\n", "import numpy as np\nfrom scipy import ndimage\n\ndef advice(agents, n):\n\ttown = np.ones((n, n)) if n else np.zeros((1, 1))\n\tfor (x, y) in agents:\n\t\tif x < n and y < n:\n\t\t\ttown[x, y] = 0\n\td = ndimage.distance_transform_cdt(town, metric='taxicab')\n\treturn list(zip(*np.where(d == d.max()))) if d.max() else []\n", "def advice(agents, n):\n\tagents = [(r, c) for (r, c) in agents if 0 <= r < n and 0 <= c < n]\n\tif n == 0 or len(set(agents)) == n * n:\n\t\treturn []\n\tfield = [[0 for _ in range(n)] for _ in range(n)]\n\tedges = []\n\tfor (r, c) in agents:\n\t\tfield[r][c] = 1\n\t\tedges.append((r, c))\n\tprevious_edges = [(r, c) for r in range(n) for c in range(n)]\n\twhile edges:\n\t\tnew_edges = []\n\t\tfor (r, c) in edges:\n\t\t\tfor (dr, dc) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n\t\t\t\t(rr, cc) = (r + dr, c + dc)\n\t\t\t\tif 0 <= rr < n and 0 <= cc < n and (field[rr][cc] == 0):\n\t\t\t\t\tfield[rr][cc] = 1\n\t\t\t\t\tnew_edges.append((rr, cc))\n\t\t(previous_edges, edges) = (edges, new_edges)\n\treturn previous_edges\n", "from itertools import starmap, product, count\n\ndef _complex_to_point(c):\n\treturn (int(c.real), int(c.imag))\n\ndef _neighbors(point):\n\treturn (point + 1j ** i for i in range(4))\n\ndef advice(agents, n):\n\tif not n:\n\t\treturn []\n\tcity = {complex(i, j): None for (i, j) in product(list(range(n)), repeat=2)}\n\tlast = set((agent for agent in starmap(complex, agents) if agent in city))\n\tif not last:\n\t\treturn sorted((_complex_to_point(cell) for cell in city))\n\tfor dist in count():\n\t\tcity.update({cell: dist for cell in last})\n\t\tnext_cells = set((neighbor for cell in last for neighbor in _neighbors(cell) if neighbor in city and city[neighbor] is None))\n\t\tif not next_cells:\n\t\t\treturn [] if not dist else sorted((_complex_to_point(cell) for cell in last))\n\t\tlast = next_cells\n", "from collections import deque\nINF = 1000000\n\nclass Field:\n\n\tdef __init__(self, n, agents):\n\t\tself.n = n\n\t\tself.agents = agents\n\t\tself.table = [[INF] * n for _ in range(n)]\n\t\tself._queue = deque()\n\t\tself._calculate_safety()\n\n\tdef _calculate_safety(self):\n\t\tfor (i, j) in self.agents:\n\t\t\tif 0 <= i < self.n and 0 <= j < self.n:\n\t\t\t\tself._add_to_queue(i, j, 0)\n\t\tself._process_queue()\n\n\tdef _add_to_queue(self, i, j, value):\n\t\tself._queue.append((i, j, value))\n\n\tdef _process_queue(self):\n\t\twhile self._queue:\n\t\t\t(i, j, value) = self._queue.popleft()\n\t\t\tif self.table[i][j] != INF:\n\t\t\t\tcontinue\n\t\t\tself.table[i][j] = value\n\t\t\tif i < self.n - 1:\n\t\t\t\tself._add_to_queue(i + 1, j, value + 1)\n\t\t\tif i > 0:\n\t\t\t\tself._add_to_queue(i - 1, j, value + 1)\n\t\t\tif j < self.n - 1:\n\t\t\t\tself._add_to_queue(i, j + 1, value + 1)\n\t\t\tif j > 0:\n\t\t\t\tself._add_to_queue(i, j - 1, value + 1)\n\n\t@property\n\tdef safest_places(self):\n\t\tlocations = []\n\t\tmax_el = 1\n\t\tfor i in range(self.n):\n\t\t\tfor j in range(self.n):\n\t\t\t\tif self.table[i][j] > max_el:\n\t\t\t\t\tmax_el = self.table[i][j]\n\t\t\t\t\tlocations = [(i, j)]\n\t\t\t\telif self.table[i][j] == max_el:\n\t\t\t\t\tlocations.append((i, j))\n\t\treturn locations\n\ndef advice(agents, n):\n\tfield = Field(n, agents)\n\treturn field.safest_places\n", "def advice(agents, n):\n\tif n <= 0:\n\t\treturn []\n\tcity = [[-1] * n for _ in range(n)]\n\tagents = [(i, j) for (i, j) in agents if i >= 0 and j >= 0 and (i < n) and (j < n)]\n\td = 0\n\twhile agents:\n\t\tt = []\n\t\tfor (i, j) in agents:\n\t\t\tcity[i][j] = d\n\t\td += 1\n\t\tfor (i, j) in agents:\n\t\t\tfor (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n\t\t\t\t(x, y) = (i + di, j + dj)\n\t\t\t\tif x < 0 or y < 0 or x >= n or (y >= n) or (city[x][y] >= 0):\n\t\t\t\t\tcontinue\n\t\t\t\tcity[x][y] = d\n\t\t\t\tt.append((x, y))\n\t\tagents = t\n\tm = max((max(r) for r in city))\n\treturn [(i, j) for i in range(n) for j in range(n) if city[i][j] == m] if m != 0 else []\n", "def advice(agents, n):\n\tA = {(i, j) for (i, j) in agents if 0 <= i < n and 0 <= j < n}\n\tB = {(i, j) for i in range(n) for j in range(n)}\n\tif A == B:\n\t\treturn []\n\twhile len(A) > 0 and A != B:\n\t\tB = B - A\n\t\tA = {(i, j) for (i, j) in B if (i + 1, j) in A or (i - 1, j) in A or (i, j + 1) in A or ((i, j - 1) in A)}\n\treturn sorted(list(B))\n"]

starter_code: def advice(agents, n):

difficulty: EASY

source: codewars

raw_problem:
Laura Bassi was the first female professor at a European university.
Despite her immense intellect, she was not always allowed to lecture publicly.

One day a professor with very strong beliefs against women in academia sent some `agents` to find Bassi and end her career.

Help her escape by telling her the safest places in town!

Task

```if:python,javascript
Implement the function `advice(agents, n)` where
```
```if:haskell
Implement the function `advice agents n :: [(Int,Int)] -> Int -> [(Int,Int)]` where
```
```if:swift
Implement the function `advice(agents: [[Int]], n: Int) -> [[Int]]` where
```

- `agents` is an array of agent coordinates.
- `n` defines the size of the city that Bassi needs to hide in, in other words the side length of the square grid.

The function should return a list of coordinates that are the furthest away (by Manhattan distance) from all agents.

As an example, say you have a 6x6 map, and agents at locations

```python
[(0, 0), (1, 5), (5, 1)]
```
```javascript
[[0, 0], [1, 5], [5, 1]]
```
```haskell
[(0, 0), (1, 5), (5, 1)]
```

The distances to the nearest agent look like this.

The safest spaces are the ones with distance `4`, marked in bright red. So the function should return

```python
[(2, 2), (3, 3), (4, 4), (5, 5)]
```
```javascript
[[2, 2], [3, 3], [4, 4], [5, 5]]
```
```haskell
[(2, 2), (3, 3), (4, 4), (5, 5)]
```

in any order.

Edge cases:
- If there is an agent on every grid cell, there is no safe space, so return an empty list.
- If there are no agents, then every cell is a safe spaces, so return all coordinates.
- if `n` is `0`, return an empty list.
- If agent coordinates are outside of the map, they are simply not considered.
- There are no duplicate agents on the same square.

Performance

You will probably not pass the tests if you use a brute-force solution.
In other words, you need to do better than `O(agents*n*n)`.

This kata is inspired by ThoughtWorks' coding challenge

question:
Laura Bassi was the first female professor at a European university.
Despite her immense intellect, she was not always allowed to lecture publicly.

One day a professor with very strong beliefs against women in academia sent some `agents` to find Bassi and end her career.

Help her escape by telling her the safest places in town!

Task

Implement the function `advice(agents, n)` where

- `agents` is an array of agent coordinates.
- `n` defines the size of the city that Bassi needs to hide in, in other words the side length of the square grid.

The function should return a list of coordinates that are the furthest away (by Manhattan distance) from all agents.

As an example, say you have a 6x6 map, and agents at locations

[(0, 0), (1, 5), (5, 1)]

The distances to the nearest agent look like this.

![image](1.png)

The safest spaces are the ones with distance `4`, marked in bright red. So the function should return
[(2, 2), (3, 3), (4, 4), (5, 5)]

in any order.

Edge cases:
- If there is an agent on every grid cell, there is no safe space, so return an empty list.
- If there are no agents, then every cell is a safe spaces, so return all coordinates.
- if `n` is `0`, return an empty list.
- If agent coordinates are outside of the map, they are simply not considered.
- There are no duplicate agents on the same square.

Performance

You will probably not pass the tests if you use a brute-force solution.
In other words, you need to do better than `O(agents*n*n)`.

data_split: test


solutions: ["import sys\ninput = sys.stdin.readline\n(n, m) = map(int, input().split())\nG = [[] for _ in range(n)]\nfor _ in range(m):\n\t(u, v) = map(int, input().split())\n\tu -= 1\n\tv -= 1\n\tG[u].append(v)\n\tG[v].append(u)\nseen = [-1] * n\n(p, q, r) = (0, 0, 0)\n\ndef dfs(v):\n\tglobal p, q\n\tstack = [(v, 0)]\n\tseen[v] = 0\n\tf = False\n\twhile stack:\n\t\t(v, c) = stack.pop()\n\t\tfor nv in G[v]:\n\t\t\tif seen[nv] == -1:\n\t\t\t\tseen[nv] = c ^ 1\n\t\t\t\tstack.append((nv, c ^ 1))\n\t\t\telif seen[nv] ^ c == 0:\n\t\t\t\tf = True\n\tif f:\n\t\tp += 1\n\telse:\n\t\tq += 1\nfor v in range(n):\n\tif seen[v] != -1:\n\t\tcontinue\n\tif not G[v]:\n\t\tr += 1\n\telse:\n\t\tdfs(v)\nans = r * (2 * n - r) + (p + q) * (p + q) + q * q\nprint(ans)\n", "(n, m) = map(int, input().split())\nab = [list(map(int, input().split())) for i in range(m)]\ngraph = [[] for i in range(n + 1)]\nfor (a, b) in ab:\n\tgraph[a].append(b)\n\tgraph[b].append(a)\n(l, s, c) = (0, 0, 0)\nvis = [-1] * (n + 1)\nstack = []\nfor i in range(1, n + 1):\n\tif vis[i] == -1:\n\t\tstack.append(i)\n\t\tflg = 0\n\t\tvis[i] = 1\n\t\twhile stack:\n\t\t\tx = stack.pop()\n\t\t\tif not graph[x]:\n\t\t\t\tflg = 2\n\t\t\tfor y in graph[x]:\n\t\t\t\tif vis[y] == -1:\n\t\t\t\t\tvis[y] = vis[x] + 1\n\t\t\t\t\tstack.append(y)\n\t\t\t\telif vis[y] % 2 == vis[x] % 2:\n\t\t\t\t\tflg = 1\n\t\tif flg == 0:\n\t\t\ts += 1\n\t\tif flg == 1:\n\t\t\tc += 1\n\t\tif flg == 2:\n\t\t\tl += 1\nprint(2 * n * l - l ** 2 + 2 * s * s + (s + c) ** 2 - s ** 2)\n", "mod = 1000000007\neps = 10 ** (-9)\n\ndef main():\n\timport sys\n\tfrom collections import deque\n\tinput = sys.stdin.buffer.readline\n\t(N, M) = map(int, input().split())\n\tadj = [[] for _ in range(N + 1)]\n\tfor _ in range(M):\n\t\t(a, b) = map(int, input().split())\n\t\tadj[a].append(b)\n\t\tadj[b].append(a)\n\tseen = [0] * (N + 1)\n\tsingle = 0\n\tbipartite = 0\n\tnot_bipartite = 0\n\tfor v0 in range(1, N + 1):\n\t\tif seen[v0] != 0:\n\t\t\tcontinue\n\t\tflg = 1\n\t\tque = deque()\n\t\tque.append(v0)\n\t\tseen[v0] = 1\n\t\tcnt = 0\n\t\twhile que:\n\t\t\tv = que.popleft()\n\t\t\tcnt += 1\n\t\t\tfor u in adj[v]:\n\t\t\t\tif seen[u] == 0:\n\t\t\t\t\tseen[u] = -seen[v]\n\t\t\t\t\tque.append(u)\n\t\t\t\telif seen[u] == seen[v]:\n\t\t\t\t\tflg = 0\n\t\tif cnt == 1:\n\t\t\tsingle += 1\n\t\telif flg:\n\t\t\tbipartite += 1\n\t\telse:\n\t\t\tnot_bipartite += 1\n\tans = N ** 2 - (N - single) ** 2\n\tans += (bipartite + not_bipartite) ** 2\n\tans += bipartite ** 2\n\tprint(ans)\nmain()\n", "import sys\ninput = sys.stdin.readline\n(N, M) = map(int, input().split())\ngraph = [[] for _ in range(N)]\nfor _ in range(M):\n\t(a, b) = map(int, input().split())\n\tgraph[a - 1].append(b - 1)\n\tgraph[b - 1].append(a - 1)\nD = [-1] * N\n\ndef bfs(s):\n\tisBi = True\n\tq = [s]\n\tD[s] = 0\n\td = 0\n\twhile q:\n\t\tqq = []\n\t\td ^= 1\n\t\tfor p in q:\n\t\t\tfor np in graph[p]:\n\t\t\t\tif D[np] == -1:\n\t\t\t\t\tD[np] = d\n\t\t\t\t\tqq.append(np)\n\t\t\t\telif D[np] != d:\n\t\t\t\t\tisBi = False\n\t\tq = qq\n\treturn isBi\na = 0\nb = 0\nc = 0\nfor n in range(N):\n\tif D[n] == -1:\n\t\tif len(graph[n]) == 0:\n\t\t\tc += 1\n\t\telif bfs(n):\n\t\t\ta += 1\n\t\telse:\n\t\t\tb += 1\nans = 2 * a ** 2 + 2 * a * b + b ** 2 + 2 * N * c - c ** 2\nprint(ans)\n", "import queue\n(n, m) = map(int, input().split())\n(vis, ci, cb, cc) = ([0] * (n + 1), 0, 0, 0)\ng = [[] for i in range(n + 1)]\n\ndef dfs(x):\n\t(stk, flag) = (queue.LifoQueue(), True)\n\tstk.put((x, 1))\n\twhile not stk.empty():\n\t\t(u, col) = stk.get()\n\t\tif vis[u]:\n\t\t\tflag &= vis[u] == col\n\t\t\tcontinue\n\t\tvis[u] = col\n\t\tfor i in g[u]:\n\t\t\tstk.put((i, 3 - col))\n\treturn flag\nfor i in range(m):\n\t(u, v) = map(int, input().split())\n\tg[u] += [v]\n\tg[v] += [u]\nfor i in range(1, n + 1):\n\tif vis[i] == 0:\n\t\tif len(g[i]) == 0:\n\t\t\tci += 1\n\t\telif dfs(i):\n\t\t\tcb += 1\n\t\telse:\n\t\t\tcc += 1\nprint(ci * ci + 2 * ci * (n - ci) + cc * cc + 2 * cb * cc + 2 * cb * cb)\n", "import sys\nread = sys.stdin.buffer.read\nreadline = sys.stdin.buffer.readline\nreadlines = sys.stdin.buffer.readlines\n(N, M) = map(int, readline().split())\nm = map(int, read().split())\nG = [[] for _ in range(N + 1)]\nfor (a, b) in zip(m, m):\n\tG[a].append(b)\n\tG[b].append(a)\ncomp = [0] * (N + 1)\ncomp_size = [0] * (N + 1)\nis_bipartite = [1] * (N + 1)\ncolor = [0] * (N + 1)\nfor r in range(1, N + 1):\n\tif comp[r]:\n\t\tcontinue\n\tcomp[r] = r\n\tcomp_size[r] = 1\n\tstack = [r]\n\twhile stack:\n\t\tv = stack.pop()\n\t\tfor w in G[v]:\n\t\t\tif comp[w]:\n\t\t\t\tif color[v] == color[w]:\n\t\t\t\t\tis_bipartite[r] = 0\n\t\t\t\tcontinue\n\t\t\tcomp[w] = r\n\t\t\tcomp_size[r] += 1\n\t\t\tcolor[w] = 1 ^ color[v]\n\t\t\tstack.append(w)\n(a, b, c) = (0, 0, 0)\nfor r in range(1, N + 1):\n\tif r != comp[r]:\n\t\tcontinue\n\tif comp_size[r] == 1:\n\t\ta += 1\n\telif is_bipartite[r]:\n\t\tc += 1\n\telse:\n\t\tb += 1\nx = 2 * a * N - a * a + b * b + 2 * b * c + 2 * c * c\nprint(x)\n", "class UnionFind:\n\n\tdef __init__(self, n):\n\t\tself.v = [-1 for _ in range(n)]\n\n\tdef find(self, x):\n\t\tif self.v[x] < 0:\n\t\t\treturn x\n\t\telse:\n\t\t\tself.v[x] = self.find(self.v[x])\n\t\t\treturn self.v[x]\n\n\tdef unite(self, x, y):\n\t\tx = self.find(x)\n\t\ty = self.find(y)\n\t\tif x == y:\n\t\t\treturn\n\t\tif -self.v[x] < -self.v[y]:\n\t\t\t(x, y) = (y, x)\n\t\tself.v[x] += self.v[y]\n\t\tself.v[y] = x\n\n\tdef root(self, x):\n\t\treturn self.v[x] < 0\n\n\tdef same(self, x, y):\n\t\treturn self.find(x) == self.find(y)\n\n\tdef size(self, x):\n\t\treturn -self.v[self.find(x)]\n(N, M) = map(int, input().split())\nuf = UnionFind(2 * N)\nfor _ in range(M):\n\t(u, v) = map(int, input().split())\n\tu -= 1\n\tv -= 1\n\tuf.unite(u, N + v)\n\tuf.unite(N + u, v)\nalone = 0\nbi = 0\nunko = 0\nfor u in range(N):\n\tif uf.root(u) or uf.root(N + u):\n\t\tif uf.size(u) == 1:\n\t\t\talone += 1\n\t\telif uf.same(u, N + u):\n\t\t\tunko += 1\n\t\telse:\n\t\t\tbi += 1\nans = 0\nans += alone * N\nans += N * alone\nans -= alone * alone\nans += bi * bi * 2\nans += bi * unko\nans += unko * bi\nans += unko * unko\nprint(ans)\n", "class UnionFind:\n\n\tdef __init__(self, n):\n\t\tself.parent = [-1] * n\n\t\tself.cnt = n\n\n\tdef root(self, x):\n\t\tif self.parent[x] < 0:\n\t\t\treturn x\n\t\telse:\n\t\t\tself.parent[x] = self.root(self.parent[x])\n\t\t\treturn self.parent[x]\n\n\tdef merge(self, x, y):\n\t\tx = self.root(x)\n\t\ty = self.root(y)\n\t\tif x == y:\n\t\t\treturn\n\t\tif self.parent[x] > self.parent[y]:\n\t\t\t(x, y) = (y, x)\n\t\tself.parent[x] += self.parent[y]\n\t\tself.parent[y] = x\n\t\tself.cnt -= 1\n\n\tdef is_same(self, x, y):\n\t\treturn self.root(x) == self.root(y)\n\n\tdef get_size(self, x):\n\t\treturn -self.parent[self.root(x)]\n\n\tdef get_cnt(self):\n\t\treturn self.cnt\n\ndef is_bipartite(graph, s):\n\tn = len(graph)\n\tstack = [s]\n\tvisited[s] = 0\n\tis_bi = True\n\twhile stack:\n\t\tv = stack.pop()\n\t\tfor nxt_v in graph[v]:\n\t\t\tif visited[nxt_v] == -1:\n\t\t\t\tvisited[nxt_v] = visited[v] ^ 1\n\t\t\t\tstack.append(nxt_v)\n\t\t\telif visited[nxt_v] ^ visited[v] == 0:\n\t\t\t\tis_bi = False\n\treturn is_bi\n(n, m) = map(int, input().split())\nedges = [list(map(int, input().split())) for i in range(m)]\nuf = UnionFind(n)\ngraph = [[] for i in range(n)]\nfor (a, b) in edges:\n\ta -= 1\n\tb -= 1\n\tuf.merge(a, b)\n\tgraph[a].append(b)\n\tgraph[b].append(a)\ncnt1 = 0\nfor v in range(n):\n\tif uf.get_size(v) == 1:\n\t\tcnt1 += 1\ncnt_bi = 0\ncnt_not_bi = 0\nvisited = [-1] * n\nfor v in range(n):\n\tif visited[v] == -1:\n\t\tflag = is_bipartite(graph, v)\n\t\tif uf.get_size(v) == 1:\n\t\t\tcontinue\n\t\tif flag:\n\t\t\tcnt_bi += 1\n\t\telse:\n\t\t\tcnt_not_bi += 1\nans = n ** 2 - (n - cnt1) ** 2\ncnt = cnt_bi + cnt_not_bi\nans += 2 * cnt_bi ** 2 + cnt ** 2 - cnt_bi ** 2\nprint(ans)\n", "import sys\nreadline = sys.stdin.readline\n\ndef check(s, Edge):\n\tstack = [s]\n\tcol[s] = False\n\tres = True\n\twhile stack:\n\t\tvn = stack.pop()\n\t\tfor vf in Edge[vn]:\n\t\t\tif vf in used:\n\t\t\t\tif col[vn] == col[vf]:\n\t\t\t\t\tres = False\n\t\t\telse:\n\t\t\t\tcol[vf] = not col[vn]\n\t\t\t\tused.add(vf)\n\t\t\t\tstack.append(vf)\n\treturn res\n(N, M) = map(int, readline().split())\nEdge = [[] for _ in range(N)]\nfor _ in range(M):\n\t(a, b) = map(int, readline().split())\n\ta -= 1\n\tb -= 1\n\tEdge[a].append(b)\n\tEdge[b].append(a)\nbip = 0\nnb = 0\npo = 0\nused = set()\ncol = [None] * N\nfor i in range(N):\n\tif i in used:\n\t\tcontinue\n\tused.add(i)\n\tif not Edge[i]:\n\t\tpo += 1\n\t\tcontinue\n\tif check(i, Edge):\n\t\tbip += 1\n\telse:\n\t\tnb += 1\nprint(2 * bip ** 2 + 2 * nb * bip + nb ** 2 + N ** 2 - (N - po) ** 2)\n", "import sys\ninput = sys.stdin.readline\n(N, M) = map(int, input().split())\nedge = [[] for i in range(N)]\nfor i in range(M):\n\t(u, v) = map(int, input().split())\n\tedge[u - 1].append(v - 1)\n\tedge[v - 1].append(u - 1)\n\ndef is_bipartgraph():\n\tcolor = [0] * N\n\tused = [False] * N\n\tb = 0\n\tnb = 0\n\tfor i in range(N):\n\t\tif not used[i]:\n\t\t\tflag = True\n\t\t\tstack = [(i, 1)]\n\t\t\tblack = 0\n\t\t\twhite = 0\n\t\t\twhile stack:\n\t\t\t\t(v, c) = stack.pop()\n\t\t\t\tif not used[v]:\n\t\t\t\t\tcolor[v] = c\n\t\t\t\t\tblack += c == 1\n\t\t\t\t\twhite += c == -1\n\t\t\t\t\tused[v] = True\n\t\t\t\t\tfor nv in edge[v]:\n\t\t\t\t\t\tif color[nv] == color[v]:\n\t\t\t\t\t\t\tflag = False\n\t\t\t\t\t\telif color[nv] == 0:\n\t\t\t\t\t\t\tstack.append((nv, -c))\n\t\t\tb += flag\n\t\t\tnb += not flag\n\treturn (b, nb)\na = 0\nfor i in range(N):\n\tif not edge[i]:\n\t\ta += 1\n(b, nb) = is_bipartgraph()\nrest = N - (b + nb)\nb -= a\nprint(a * N + nb * (a + nb + b) + b * (a + nb + 2 * b) + rest * a)\n", "(n, m) = map(int, input().split())\n(vis, ci, cb, cc) = ([0] * (n + 1), 0, 0, 0)\ng = [[] for i in range(n + 1)]\nfor i in range(m):\n\t(u, v) = map(int, input().split())\n\tg[u] += [v]\n\tg[v] += [u]\nfor i in range(1, n + 1):\n\tif vis[i] == 0:\n\t\tif len(g[i]) == 0:\n\t\t\tci += 1\n\t\telse:\n\t\t\t(s, f) = ([(i, 1)], True)\n\t\t\twhile len(s):\n\t\t\t\t(u, col) = s.pop()\n\t\t\t\tif vis[u]:\n\t\t\t\t\tf &= vis[u] == col\n\t\t\t\t\tcontinue\n\t\t\t\tvis[u] = col\n\t\t\t\tfor i in g[u]:\n\t\t\t\t\ts += [(i, 3 - col)]\n\t\t\tcb += f\n\t\t\tcc += f ^ 1\nprint(ci * ci + 2 * ci * (n - ci) + cc * cc + 2 * cb * cc + 2 * cb * cb)\n", "import sys\ninput = lambda : sys.stdin.readline().rstrip()\nsys.setrecursionlimit(max(1000, 10 ** 9))\nwrite = lambda x: sys.stdout.write(x + '\\n')\n(n, m) = list(map(int, input().split()))\nfrom collections import defaultdict\nns = defaultdict(set)\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\ta -= 1\n\tb -= 1\n\tns[a].add(b)\n\tns[b].add(a)\ncs = [None] * n\n\ndef is_bip(u):\n\tq = [start]\n\tcs[start] = 1\n\tv1 = 1\n\tv0 = 0\n\tbip = True\n\twhile q:\n\t\tu = q.pop()\n\t\tc = cs[u]\n\t\tcc = int(not c)\n\t\tfor v in ns[u]:\n\t\t\tif cs[v] is None:\n\t\t\t\tcs[v] = cc\n\t\t\t\tif cc == 0:\n\t\t\t\t\tv0 += 1\n\t\t\t\telse:\n\t\t\t\t\tv1 += 1\n\t\t\t\tq.append(v)\n\t\t\telif cs[v] == c:\n\t\t\t\tbip = False\n\tif bip:\n\t\treturn (True, v0, v1)\n\telse:\n\t\treturn (False, v0 + v1, 0)\ntypes = []\nvals = []\nans = 0\nn0 = 0\nn1 = 0\nn2 = 0\nnv = 0\nfor start in range(n):\n\tif cs[start] is not None:\n\t\tcontinue\n\t(res, v0, v1) = is_bip(start)\n\tif v0 + v1 == 1:\n\t\tn0 += 1\n\telif res:\n\t\tnv += v0 + v1\n\t\tn1 += 1\n\telse:\n\t\tnv += v0 + v1\n\t\tn2 += 1\nans += n0 * nv * 2\nans += n0 ** 2\nans += (n1 + n2) ** 2 + n1 ** 2\nprint(ans)\n", "import sys\n\ndef check_bipartite(s, links, visited):\n\tq = [(s, 0)]\n\tis_bipartite = True\n\tcount = 0\n\twhile q:\n\t\t(v, color) = q.pop()\n\t\tif visited[v] != -1:\n\t\t\tif visited[v] != color:\n\t\t\t\tis_bipartite = False\n\t\t\tcontinue\n\t\tvisited[v] = color\n\t\tcount += 1\n\t\tnew_color = color ^ 1\n\t\tfor u in links[v]:\n\t\t\tif visited[u] != -1:\n\t\t\t\tif visited[u] != new_color:\n\t\t\t\t\tis_bipartite = False\n\t\t\t\tcontinue\n\t\t\tq.append((u, new_color))\n\treturn (is_bipartite, count)\n(n, m) = map(int, sys.stdin.buffer.readline().split())\nlinks = [set() for _ in range(n)]\nmp = map(int, sys.stdin.buffer.read().split())\nfor (u, v) in zip(mp, mp):\n\tu -= 1\n\tv -= 1\n\tlinks[u].add(v)\n\tlinks[v].add(u)\nvisited = [-1] * n\ncount_bipartite = 0\ncount_non_bipartite = 0\ncount_isolated = 0\nans = 0\nfor v in range(n):\n\tif visited[v] != -1:\n\t\tcontinue\n\t(is_bipartite, count) = check_bipartite(v, links, visited)\n\tif count == 1:\n\t\tcount_isolated += 1\n\telif is_bipartite:\n\t\tcount_bipartite += 1\n\telse:\n\t\tcount_non_bipartite += 1\nans = count_isolated * (n * 2 - count_isolated)\nans += count_non_bipartite * (count_non_bipartite + count_bipartite * 2)\nans += count_bipartite ** 2 * 2\nprint(ans)\n", "import sys\ninput = sys.stdin.readline\n(N, M) = map(int, input().split())\nUV = [[int(x) for x in row.split()] for row in sys.stdin.readlines()]\ngraph = [[] for _ in range(N + 1)]\nfor (u, v) in UV:\n\tgraph[u].append(v)\n\tgraph[v].append(u)\ncolor = [None] * (N + 1)\n\ndef calc_comp_data(v):\n\tc = 0\n\tq = [v]\n\tcolor[v] = 0\n\tis_bipartite = True\n\tsize = 1\n\twhile q:\n\t\tqq = []\n\t\tc ^= 1\n\t\tfor x in q:\n\t\t\tfor y in graph[x]:\n\t\t\t\tif color[y] is None:\n\t\t\t\t\tcolor[y] = c\n\t\t\t\t\tqq.append(y)\n\t\t\t\t\tsize += 1\n\t\t\t\telif color[y] == c:\n\t\t\t\t\tcontinue\n\t\t\t\telse:\n\t\t\t\t\tis_bipartite = False\n\t\tq = qq\n\treturn (size, is_bipartite)\nsize = []\nis_bipartite = []\nfor v in range(1, N + 1):\n\tif color[v] is not None:\n\t\tcontinue\n\t(x, y) = calc_comp_data(v)\n\tsize.append(x)\n\tis_bipartite.append(y)\n(size, is_bipartite)\nn_point = sum((1 if s == 1 else 0 for s in size))\nn_component = len(size)\nn_bipartitle = sum((1 if s >= 2 and bl else 0 for (s, bl) in zip(size, is_bipartite)))\nanswer = 0\nfor (s, bl) in zip(size, is_bipartite):\n\tif s == 1:\n\t\tanswer += N\n\telif not bl:\n\t\tanswer += n_component - n_point + s * n_point\n\telse:\n\t\tanswer += n_component - n_point + n_bipartitle + s * n_point\nprint(answer)\n"]

name: AtCoder Grand Contest 011 - Squared Graph

source: atcoder

time_limit: 2.0 seconds

memory_limit: 256.0 megabytes

raw_problem:
配点 : <var>800</var> 点

問題文

高橋君は，<var>N</var> 頂点 <var>1</var>, <var>2</var>, ..., <var>N</var> からなる無向グラフをもらいました．
このグラフの辺は <var>(u_i, v_i)</var> で表されます．
このグラフには，自己辺や多重辺は存在しません．

高橋君は，このグラフをもとに，<var>N^2</var> 頂点 <var>(a, b)</var> (<var>1 \leq a \leq N</var>, <var>1 \leq b \leq N</var>) からなるグラフを作ることにしました．
このグラフの辺は，次の規則で定まります．

元のグラフにおいて <var>a</var> と <var>a'</var> の間および <var>b</var> と <var>b'</var> の間の両方に辺があるとき，またそのときに限り，<var>(a, b)</var> と <var>(a', b')</var> の間に辺を張る．

このようにして作ったグラフの連結成分の個数を求めてください．

制約

<var>2 \leq N \leq 100,000</var>

<var>0 \leq M \leq 200,000</var>

<var>1 \leq u_i < v_i \leq N</var>

<var>u_i = u_j</var> かつ <var>v_i = v_j</var> を満たすような異なる <var>i, j</var> の組は存在しない

入力

入力は以下の形式で標準入力から与えられる。

<var>N</var> <var>M</var>
<var>u_1</var> <var>v_1</var>
<var>u_2</var> <var>v_2</var>
:
<var>u_M</var> <var>v_M</var>

出力

高橋君の作ったグラフの連結成分の個数を出力せよ．

入力例 1

3 1
1 2

出力例 1

7

高橋君の作ったグラフは下のようになります．

入力例 2

7 5
1 2
3 4
3 5
4 5
2 6

出力例 2

18

Score : <var>800</var> points

Problem Statement

Takahashi has received an undirected graph with <var>N</var> vertices, numbered <var>1</var>, <var>2</var>, ..., <var>N</var>.
The edges in this graph are represented by <var>(u_i, v_i)</var>.
There are no self-loops and multiple edges in this graph.

Based on this graph, Takahashi is now constructing a new graph with <var>N^2</var> vertices, where each vertex is labeled with a pair of integers <var>(a, b)</var> (<var>1 \leq a \leq N</var>, <var>1 \leq b \leq N</var>).
The edges in this new graph are generated by the following rule:

Span an edge between vertices <var>(a, b)</var> and <var>(a', b')</var> if and only if both of the following two edges exist in the original graph: an edge between vertices <var>a</var> and <var>a'</var>, and an edge between vertices <var>b</var> and <var>b'</var>.

How many connected components are there in this new graph?

Constraints

<var>2 \leq N \leq 100,000</var>

<var>0 \leq M \leq 200,000</var>

<var>1 \leq u_i < v_i \leq N</var>

There exists no pair of distinct integers <var>i</var> and <var>j</var> such that <var>u_i = u_j</var> and <var>v_i = v_j</var>.

Input

The input is given from Standard Input in the following format:

<var>N</var> <var>M</var>
<var>u_1</var> <var>v_1</var>
<var>u_2</var> <var>v_2</var>
:
<var>u_M</var> <var>v_M</var>

Output

Print the number of the connected components in the graph constructed by Takahashi.

Sample Input 1

3 1
1 2

Sample Output 1

7

The graph constructed by Takahashi is as follows.

Sample Input 2

7 5
1 2
3 4
3 5
4 5
2 6

Sample Output 2

18

question:
Takahashi has received an undirected graph with $N$ vertices, numbered $1$, $2$, ..., $N$.
The edges in this graph are represented by $(u_i, v_i)$.
There are no self-loops and multiple edges in this graph.
Based on this graph, Takahashi is now constructing a new graph with $N^2$ vertices, where each vertex is labeled with a pair of integers $(a, b)$ ($1 \leq a \leq N$, $1 \leq b \leq N$).
The edges in this new graph are generated by the following rule:

- Span an edge between vertices $(a, b)$ and $(a', b')$ if and only if both of the following two edges exist in the original graph: an edge between vertices $a$ and $a'$, and an edge between vertices $b$ and $b'$.

How many connected components are there in this new graph?

Constraints

- $2 \leq N \leq 100,000$
- $0 \leq M \leq 200,000$
- $1 \leq u_i < v_i \leq N$
- There exists no pair of distinct integers $i$ and $j$ such that $u_i = u_j$ and $v_i = v_j$.

Input
The input is given from Standard Input in the following format:
$N$ $M$

$u_1$ $v_1$

$u_2$ $v_2$
:

$u_M$ $v_M$

Output
Print the number of the connected components in the graph constructed by Takahashi.

Sample Input 1
3 1
1 2

Sample Output 1
7

The graph constructed by Takahashi is as follows.
![image](1.png)

Sample Input 2
7 5
1 2
3 4
3 5
4 5
2 6

Sample Output 2
18

data_split: test


problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
In the first sample, there is only 1 tree with 2 nodes (node 1 connected to node 2). The algorithm will produce a correct answer in it so we printed  - 1 in the first section, but notice that we printed this tree in the second section.
In the second sample:
In the first tree, the algorithm will find an answer with 4 nodes, while there exists an answer with 3 nodes like this: ![image](images/cf_959_C/1.png) In the second tree, the algorithm will find an answer with 3 nodes which is correct: ![image](images/cf_959_C/2.png)

solutions: ["from sys import stdin, stdout\nn = int(stdin.readline())\nif n <= 5:\n\tstdout.write('-1\\n')\n\tfor i in range(n - 1):\n\t\tstdout.write(str(i + 1) + ' ' + str(i + 2) + '\\n')\nelse:\n\tif n & 1:\n\t\tlast = 0\n\t\tfor i in range(n // 2 + 1):\n\t\t\tstdout.write('1 ' + str(i + 2) + '\\n')\n\t\t\tlast = i + 3\n\t\tfor i in range(n // 2 - 1):\n\t\t\tstdout.write('2 ' + str(last) + '\\n')\n\t\t\tlast += 1\n\telse:\n\t\tlast = 0\n\t\tfor i in range(n // 2):\n\t\t\tstdout.write('1 ' + str(i + 2) + '\\n')\n\t\t\tlast = i + 3\n\t\tfor i in range(n // 2 - 1):\n\t\t\tstdout.write('2 ' + str(last) + '\\n')\n\t\t\tlast += 1\n\tfor i in range(n - 1):\n\t\tstdout.write(str(i + 1) + ' ' + str(i + 2) + '\\n')\n", "from sys import stdin\nfrom collections import deque\nmod = 10 ** 9 + 7\nimport sys\nsys.setrecursionlimit(10 ** 5)\nfrom queue import PriorityQueue\nfrom bisect import bisect_right\nfrom bisect import bisect_left\nfrom collections import defaultdict\nfrom math import sqrt, factorial, gcd, log2, inf, ceil\nimport heapq\ninput = lambda : sys.stdin.readline().rstrip()\nfrom sys import stdin, stdout\nfrom heapq import heapify, heappush, heappop\nn = int(input())\nif n < 6:\n\tprint(-1)\n\tfor i in range(n - 1):\n\t\tprint(i + 1, i + 2)\nelse:\n\tfor i in range(1, 4):\n\t\tprint(1, i + 1)\n\tfor i in range(5, n + 1):\n\t\tprint(2, i)\n\tfor i in range(n - 1):\n\t\tprint(i + 1, i + 2)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom collections import Counter\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\n\ndef gcd(a, b):\n\tif a == 0:\n\t\treturn b\n\treturn gcd(b % a, a)\n\ndef lcm(a, b):\n\treturn a * b / gcd(a, b)\n\ndef main():\n\tn = int(input())\n\tif n < 6:\n\t\tprint(-1)\n\telse:\n\t\tfor i in range(2, n - 2 + 1):\n\t\t\tprint(1, i)\n\t\tprint(2, n - 1)\n\t\tprint(2, n)\n\tfor i in range(1, n):\n\t\tprint(i, i + 1)\n\treturn\nmain()\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tfor i in range(2, 5):\n\t\tprint('1 ' + str(i))\n\tfor i in range(5, n + 1):\n\t\tprint('2 ' + str(i))\nfor i in range(1, n):\n\tprint(str(i) + ' ' + str(i + 1))\n", "n = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tprint(1, 2)\n\tprint(1, 3)\n\tprint(1, 4)\n\tprint(2, 5)\n\tprint(2, 6)\n\tfor i in range(7, n + 1):\n\t\tprint(1, i)\nfor i in range(2, n + 1):\n\tprint(1, i)\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tprint(1, 2)\n\tfor i in range(3, n + 1):\n\t\tprint(i % 2 + 1, i)\nfor i in range(1, n):\n\tprint(i, i + 1)\n", "k = int(input())\nif k <= 5:\n\tprint(-1)\n\tfor i in range(2, k + 1):\n\t\tprint(1, i)\nelse:\n\tfor i in range(2, k - 1):\n\t\tprint(1, i)\n\tprint(k - 2, k - 1)\n\tprint(k - 2, k)\n\tfor i in range(2, k + 1):\n\t\tprint(1, i)\n", "n = int(input().strip())\nif n <= 5:\n\tprint(-1)\nelse:\n\tfor i in range(2, n - 1):\n\t\tprint(1, i)\n\tfor i in range(n - 1, n + 1):\n\t\tprint(2, i)\nfor i in range(1, n):\n\tprint(i, i + 1)\n", "def main():\n\tn = int(input())\n\tif n < 6:\n\t\tprint(-1)\n\telse:\n\t\tfor x in range(2, n // 2 + 2):\n\t\t\tprint(1, x)\n\t\tfor x in range(n // 2 + 2, n + 1):\n\t\t\tprint(2, x)\n\tfor x in range(n - 1):\n\t\tprint(x + 1, x + 2)\nmain()\n", "def get_correct_tree(n):\n\tfor i in range(2, n + 1):\n\t\tprint(1, i)\n\ndef get_incorrect_tree(n):\n\tif n < 6:\n\t\tprint(-1)\n\t\treturn\n\tfor i in range(2, n - 1):\n\t\tprint(1, i)\n\tprint(2, n - 1)\n\tprint(2, n)\nn = int(input())\nget_incorrect_tree(n)\nget_correct_tree(n)\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tprint('1 2')\n\tprint('1 3')\n\tprint('1 4')\n\tx = 5\n\tfor i in range(4, n):\n\t\tprint('4 %d' % x)\n\t\tx += 1\nfor j in range(1, n):\n\tprint('%d %d' % (j, j + 1))\n", "n = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tprint(str(1) + ' ' + str(2))\n\tprint(str(2) + ' ' + str(3))\n\tprint(str(2) + ' ' + str(4))\n\tprint(str(4) + ' ' + str(5))\n\tprint(str(4) + ' ' + str(6))\n\tk = 5\n\twhile k < n - 1:\n\t\tprint(str(4) + ' ' + str(k + 2))\n\t\tk += 1\nh = 0\nwhile h < n - 1:\n\tprint(str(1) + ' ' + str(h + 2))\n\th += 1\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tbaseans = [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)]\n\tfor p in baseans:\n\t\tprint('%d %d' % (p[0], p[1]))\n\tfor i in range(7, n + 1):\n\t\tprint('%d %d' % (4, i))\nfor i in range(2, n + 1):\n\tprint('%d %d' % (1, i))\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tprint('1 2\\n1 3\\n1 4')\n\tfor i in range(5, n + 1):\n\t\tprint('2 ' + str(i))\nfor i in range(2, n + 1):\n\tprint('1 ' + str(i))\n", "import sys\nfrom functools import lru_cache, cmp_to_key\nfrom heapq import merge, heapify, heappop, heappush\nfrom math import *\nfrom collections import defaultdict as dd, deque, Counter as C\nfrom itertools import combinations as comb, permutations as perm\nfrom bisect import bisect_left as bl, bisect_right as br, bisect\nfrom time import perf_counter\nfrom fractions import Fraction\nimport copy\nimport time\nstarttime = time.time()\nmod = int(pow(10, 9) + 7)\nmod2 = 998244353\n\ndef data():\n\treturn sys.stdin.readline().strip()\n\ndef out(*var, end='\\n'):\n\tsys.stdout.write(' '.join(map(str, var)) + end)\n\ndef L():\n\treturn list(sp())\n\ndef sl():\n\treturn list(ssp())\n\ndef sp():\n\treturn map(int, data().split())\n\ndef ssp():\n\treturn map(str, data().split())\n\ndef l1d(n, val=0):\n\treturn [val for i in range(n)]\n\ndef l2d(n, m, val=0):\n\treturn [l1d(n, val) for j in range(m)]\ntry:\n\tsys.stdin = open('input.txt', 'r')\nexcept:\n\tpass\nn = L()[0]\nif n < 6:\n\tprint(-1)\nelse:\n\tprint(1, 2)\n\tprint(1, 3)\n\tprint(1, 4)\n\tfor i in range(5, n + 1):\n\t\tprint(2, i)\nfor i in range(1, n):\n\tprint(i, i + 1)\nendtime = time.time()\n", "def main():\n\tn = int(input())\n\tif n < 6:\n\t\tprint(-1)\n\telse:\n\t\tprint(1, 2)\n\t\tprint(2, 3)\n\t\tprint(2, 4)\n\t\tfor i in range(5, n + 1):\n\t\t\tprint(1, i)\n\tfor i in range(1, n):\n\t\tprint(i, i + 1)\nmain()\n", "n = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tprint('1 2', '1 3', '1 4', '2 5', sep='\\n')\n\tfor i in range(6, n + 1):\n\t\tprint('2 {0:d}'.format(i))\nfor i in range(2, n + 1):\n\tprint('1 {0:d}'.format(i))\n", "n = int(input())\nans = []\nif n < 6:\n\tprint(-1)\nelse:\n\tfor i in range(2, n - 1):\n\t\tans.append('1 %i\\n' % i)\n\tans.append('2 %i\\n2 %i\\n' % (n - 1, n))\nfor i in range(2, n + 1):\n\tans.append('1 %i\\n' % i)\nprint(*ans, sep='')\n", "s = input()\nn = int(s)\n\ndef generator():\n\tif n > 5:\n\t\tyield '1 2'\n\t\tfor i in range(3, (n + 1) // 2 + 2):\n\t\t\tyield '1 {}'.format(i)\n\t\tfor i in range((n + 1) // 2 + 2, n + 1):\n\t\t\tyield '2 {}'.format(i)\n\telse:\n\t\tyield '-1'\n\tfor i in range(2, n + 1):\n\t\tyield '1 {}'.format(i)\nprint('\\n'.join(generator()))\n", "import atexit\nimport io\nimport sys\n_INPUT_LINES = sys.stdin.read().splitlines()\ninput = iter(_INPUT_LINES).__next__\n_OUTPUT_BUFFER = io.StringIO()\nsys.stdout = _OUTPUT_BUFFER\n\n@atexit.register\ndef write():\n\tsys.__stdout__.write(_OUTPUT_BUFFER.getvalue())\n\ndef main():\n\tn = int(input())\n\tif n < 6:\n\t\tprint(-1)\n\telse:\n\t\tprint('1 2')\n\t\tprint('2 3')\n\t\tprint('2 4')\n\t\tfor j in range(5, n + 1):\n\t\t\tprint(1, j)\n\tfor j in range(2, n + 1):\n\t\tprint(1, j)\nmain()\n", "import sys\nimport os.path\nfrom collections import *\nimport math\nimport bisect\nif os.path.exists('input.txt'):\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\nelse:\n\tinput = sys.stdin.readline\nn = int(input())\nif n == 2 or n == 3 or n == 4 or (n == 5):\n\tprint(-1)\nelse:\n\tprint(1, 2)\n\tprint(2, 3)\n\tprint(2, 4)\n\tfor i in range(5, n + 1):\n\t\tprint(4, i)\nfor i in range(2, n + 1):\n\tprint(1, i)\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tif n % 2 == 0:\n\t\tc = 2\n\t\tfor i in range(n // 2):\n\t\t\tprint(1, c)\n\t\t\tc += 1\n\t\tfor i in range(n // 2 - 1):\n\t\t\tprint(2, c)\n\t\t\tc += 1\n\tif n % 2 == 1:\n\t\tc = 2\n\t\tfor i in range(n // 2):\n\t\t\tprint(1, c)\n\t\t\tc += 1\n\t\tfor i in range(n // 2):\n\t\t\tprint(2, c)\n\t\t\tc += 1\nfor i in range(2, n + 1):\n\tprint(1, i)\n", "import sys\nmod = 1000000007\n\ndef get_array():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef get_ints():\n\treturn map(int, sys.stdin.readline().split())\n\ndef input():\n\treturn sys.stdin.readline()\n\ndef print_array(a):\n\tprint(' '.join(map(str, a)))\n\ndef main():\n\tn = int(input())\n\tif n < 6:\n\t\tprint('-1')\n\telse:\n\t\tprint('1 2\\n1 3\\n1 4')\n\t\tfor val in range(5, n + 1):\n\t\t\tprint('2 ' + str(val))\n\tfor val in range(2, n + 1):\n\t\tprint('1 ' + str(val))\nmain()\n", "def correct(n):\n\tfor i in range(1, n):\n\t\tprint(1, i + 1)\n\ndef incorrect(n):\n\tif n <= 5:\n\t\tprint(-1)\n\telse:\n\t\tm = int(n / 2) + 1\n\t\tfor i in range(1, m):\n\t\t\tprint(1, i + 1)\n\t\tfor i in range(m, n):\n\t\t\tprint(2, i + 1)\n\ndef main():\n\tn = int(input())\n\tincorrect(n)\n\tcorrect(n)\nmain()\n", "import sys\nfrom math import *\nreadints = lambda : map(int, input().strip('\\n').split())\nn = int(input())\n\ndef incorrect(n):\n\tif n <= 5:\n\t\tprint(-1)\n\telse:\n\t\tfor i in range(2, n - 2 + 1):\n\t\t\tprint(1, i)\n\t\tprint(2, n - 1)\n\t\tprint(2, n)\n\ndef correct(n):\n\tfor i in range(2, n + 1):\n\t\tprint(1, i)\nincorrect(n)\ncorrect(n)\n", "import sys\nlines = sys.stdin.readlines()\nn = int(lines[0].strip())\nif n <= 5:\n\tprint(-1)\nelse:\n\tprint('{} {}'.format(1, 2))\n\tfor i in range(3, n + 1):\n\t\tif i % 2 == 0:\n\t\t\tprint('{} {}'.format(i, 2))\n\t\telse:\n\t\t\tprint('{} {}'.format(i, 1))\nfor i in range(1, n):\n\tprint('{} {}'.format(i, i + 1))\n", "n = int(input())\nif n <= 5:\n\tprint(-1)\n\tfor a in range(n - 1):\n\t\tprint(a + 1, a + 2)\n\texit(0)\nprint(1, 2)\nprint(1, 3)\nprint(1, 4)\nfor i in range(5, n + 1):\n\tprint(2, i)\nfor a in range(n - 1):\n\tprint(a + 1, a + 2)\n", "n = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tprint('\\n'.join(['1 ' + str(i) for i in range(2, 5)]))\n\tend = False\n\tans = []\n\thead = 2\n\twhile True:\n\t\ti = head\n\t\tj = i + 3\n\t\twhile j <= i + 5:\n\t\t\ttmp_ans = str(i) + ' ' + str(j)\n\t\t\tans.append(tmp_ans)\n\t\t\tif j == n:\n\t\t\t\tend = True\n\t\t\t\tbreak\n\t\t\tj += 1\n\t\tif end:\n\t\t\tbreak\n\t\thead += 3\n\tprint('\\n'.join(ans))\nprint('\\n'.join(['1 ' + str(i) for i in range(2, n + 1)]))\n", "from math import ceil\nn = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tfor i in range(2, n // 2 + 2):\n\t\tprint(1, i)\n\tfor j in range(2 + n // 2, n + 1):\n\t\tprint(2, j)\nfor k in range(1, n):\n\tprint(k, k + 1)\n", "n = int(input())\n\ndef print_wrong(l):\n\tif l < 6:\n\t\tprint('-1')\n\telse:\n\t\tfor i in range(0, l - 1):\n\t\t\tif i % 2 == 0:\n\t\t\t\tfirst = '1 '\n\t\t\telse:\n\t\t\t\tfirst = '2 '\n\t\t\tprint(first + str(i + 2))\n\ndef print_right(l):\n\tfor i in range(0, l - 1):\n\t\tprint('1 %s' % str(i + 2))\nprint_wrong(n)\nprint_right(n)\n", "n = int(input())\nif n < 6:\n\tprint('-1')\nelse:\n\tk = 2\n\twhile k <= 4:\n\t\tprint('1', k)\n\t\tk += 1\n\twhile k <= n:\n\t\tprint('2', k)\n\t\tk += 1\ni = 1\nwhile i <= n - 1:\n\tprint(i, i + 1)\n\ti += 1\n", "import sys\nimport math\nMAXNUM = math.inf\nMINNUM = -1 * math.inf\nASCIILOWER = 97\nASCIIUPPER = 65\n\ndef getInt():\n\treturn int(sys.stdin.readline().rstrip())\n\ndef getInts():\n\treturn map(int, sys.stdin.readline().rstrip().split(' '))\n\ndef getString():\n\treturn sys.stdin.readline().rstrip()\n\ndef printOutput(a, b):\n\tif not a:\n\t\tsys.stdout.write(str(-1) + '\\n')\n\telse:\n\t\tfor (x, y) in a:\n\t\t\tsys.stdout.write(str(x) + ' ' + str(y) + '\\n')\n\tfor (x, y) in b:\n\t\tsys.stdout.write(str(x) + ' ' + str(y) + '\\n')\n\ndef incorrectAlg(ln):\n\tans = []\n\tfor i in range(1, ln - 3):\n\t\tans.append((1, i + 1))\n\tans.append((1, ln - 2))\n\tans.append((ln - 2, ln - 1))\n\tans.append((ln - 2, ln))\n\treturn ans\n\ndef correctAlgorithm(ln):\n\tans = []\n\tfor i in range(1, ln):\n\t\tans.append((i, i + 1))\n\treturn ans\n\ndef solve(ln):\n\tif ln < 6:\n\t\ta = None\n\telse:\n\t\ta = incorrectAlg(ln)\n\tb = correctAlgorithm(ln)\n\treturn (a, b)\n\ndef readinput():\n\tln = getInt()\n\tprintOutput(*solve(ln))\nreadinput()\n", "import sys\nimport math\nfrom collections import Counter\nfrom operator import itemgetter\nimport queue\n\ndef IO():\n\tsys.stdin = open('pyinput.txt', 'r')\n\tsys.stdout = open('pyoutput.txt', 'w')\n\ndef GCD(a, b):\n\tif b == 0:\n\t\treturn a\n\telse:\n\t\treturn GCD(b, a % b)\n\ndef LCM(a, b):\n\treturn a * (b // GCD(a, b))\n\ndef scan(TYPE_1, TYPE_2=0):\n\tif TYPE_1 == int:\n\t\treturn map(int, sys.stdin.readline().strip().split())\n\telif TYPE_1 == float:\n\t\treturn map(float, sys.stdin.readline().strip().split())\n\telif TYPE_1 == list and TYPE_2 == float:\n\t\treturn list(map(float, sys.stdin.readline().strip().split()))\n\telif TYPE_1 == list and TYPE_2 == int:\n\t\treturn list(map(int, sys.stdin.readline().strip().split()))\n\telif TYPE_1 == str:\n\t\treturn sys.stdin.readline().strip()\n\telse:\n\t\tprint('ERROR!!!!')\n\ndef main():\n\tn = int(input())\n\tif n < 6:\n\t\tprint(-1)\n\telse:\n\t\tprint(1, 2)\n\t\tprint(1, 3)\n\t\tprint(1, 4)\n\t\tfor i in range(5, n + 1):\n\t\t\tprint(4, i)\n\tfor i in range(2, n + 1):\n\t\tprint(1, i)\nmain()\n", "def wrong(x):\n\tif n < 6:\n\t\tprint(-1)\n\telse:\n\t\tprint('1 2')\n\t\tprint('2 3')\n\t\tprint('2 4')\n\t\tprint('4 5')\n\t\tprint('4 6')\n\t\tfor i in range(7, x + 1):\n\t\t\tprint('4', i)\n\ndef true(x):\n\tfor i in range(x - 1):\n\t\tprint(i + 1, i + 2)\nn = int(input())\nwrong(n)\ntrue(n)\n", "import sys\nn = int(input().strip())\nif n < 6:\n\tprint(-1)\nelse:\n\tprint(1, 2)\n\tfor i in range(3, n + 1):\n\t\tprint(i % 2 + 1, i)\nfor i in range(n - 1):\n\tprint(1, i + 2)\n", "import sys\nn = int(sys.stdin.readline())\nif n < 6:\n\tprint(-1)\nelse:\n\tprint('1 2')\n\tfor i in range(3, n + 1):\n\t\tif i % 2 == 0:\n\t\t\tprint('2 ' + str(i))\n\t\telse:\n\t\t\tprint('1 ' + str(i))\nfor i in range(2, n + 1):\n\tprint('1 ' + str(i))\n", "n = int(input())\n\ndef print_wrong(n):\n\tprint('1 2')\n\tprint('1 3')\n\tprint('1 4')\n\tprint('3 5')\n\tprint('3 6')\n\tfor i in range(7, n + 1):\n\t\tprint('1 %s' % i)\n\ndef print_correct(n):\n\tfor i in range(2, n + 1):\n\t\tprint('1 %s' % i)\nif n < 6:\n\tprint('-1')\nelse:\n\tprint_wrong(n)\nprint_correct(n)\n", "import math\nn = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tfor i in range(2, math.floor(n / 2) + 2):\n\t\tprint(1, i)\n\tfor i in range(math.floor(n / 2) + 2, n + 1):\n\t\tprint(math.floor(n / 2) + 1, i)\nfor i in range(1, n):\n\tprint(i, i + 1)\n", "n = int(input())\nif n in range(2, 5 + 1):\n\tprint('-1')\n\tfor i in range(2, n + 1):\n\t\tprint('1', i)\nelse:\n\tprint('1 2')\n\tp = n // 2 - 2\n\tfor i in range(p + 1):\n\t\tprint('2', i + 3)\n\tfor i in range(n - p - 3):\n\t\tprint('1', i + p + 4)\n\tfor i in range(n - 1):\n\t\tprint('1', i + 2)\n", "n = int(input())\nwrong = str()\nif n <= 5:\n\twrong = -1\nelse:\n\twrong = '\\n'.join([f'1 {i}' for i in range(2, n - 1)] + [f'2 {n - 1}', f'2 {n}'])\nright = '\\n'.join([f'1 {i}' for i in range(2, n + 1)])\nprint(wrong)\nprint(right)\n", "import sys\ninput = sys.stdin.readline\nn = int(input())\nif n < 6:\n\tprint(-1)\n\tfor i in range(n - 1):\n\t\tprint(i + 1, i + 2)\nelse:\n\tk = n - 2\n\tk1 = k // 2\n\tk2 = k - k1\n\tfor i in range(k1):\n\t\tprint(i + 1, n - 1)\n\tfor i in range(k1, n - 1):\n\t\tprint(i + 1, n)\n\tfor i in range(n - 1):\n\t\tprint(i + 1, i + 2)\n", "n = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tn3 = (n - 1) // 2\n\tn2 = n - n3 - 1\n\tfor i in range(n2):\n\t\tprint(1, i + 2)\n\tfor i in range(n3):\n\t\tprint(2, i + n2 + 2)\nfor i in range(n - 1):\n\tprint(1, i + 2)\n", "n = int(input())\nif n <= 5:\n\tprint(-1)\nelif n % 2 == 0:\n\tprint(1, 2)\n\tprint(2, 3)\n\tprint(2, 4)\n\tprint(4, 5)\n\tprint(4, 6)\n\tif n > 6:\n\t\tprint(1, 7)\n\t\tfor i in range(n - 7):\n\t\t\tprint(i + 7, i + 8)\nelse:\n\tprint(1, 2)\n\tprint(2, 3)\n\tprint(2, 4)\n\tprint(2, 5)\n\tprint(4, 6)\n\tprint(4, 7)\n\tif n > 7:\n\t\tprint(1, 8)\n\t\tfor i in range(n - 8):\n\t\t\tprint(i + 8, i + 9)\nfor i in range(n - 1):\n\tprint(1, i + 2)\n", "a = int(input())\nif a <= 5:\n\tprint(-1)\nelse:\n\tprint('1 2')\n\tprint('2 3')\n\tprint('2 4')\n\tprint('4 5')\n\tfor i in range(6, a + 1):\n\t\tprint('4 ' + str(i))\nfor i in range(1, a):\n\tprint(str(i) + ' ' + str(i + 1))\n", "import os\nimport sys\nimport math\nfrom io import BytesIO, IOBase\nfrom fractions import Fraction\nimport collections\nfrom itertools import permutations\nfrom collections import defaultdict\nfrom collections import deque\nimport threading\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\nclass Factorial:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorials = [1, 1]\n\t\tself.invModulos = [0, 1]\n\t\tself.invFactorial_ = [1, 1]\n\n\tdef calc(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.factorials):\n\t\t\treturn self.factorials[n]\n\t\tnextArr = [0] * (n + 1 - len(self.factorials))\n\t\tinitialI = len(self.factorials)\n\t\tprev = self.factorials[-1]\n\t\tm = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * i % m\n\t\tself.factorials += nextArr\n\t\treturn self.factorials[n]\n\n\tdef inv(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n^(-1)')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tp = self.MOD\n\t\tpi = n % p\n\t\tif pi < len(self.invModulos):\n\t\t\treturn self.invModulos[pi]\n\t\tnextArr = [0] * (n + 1 - len(self.invModulos))\n\t\tinitialI = len(self.invModulos)\n\t\tfor i in range(initialI, min(p, n + 1)):\n\t\t\tnext = -self.invModulos[p % i] * (p // i) % p\n\t\t\tself.invModulos.append(next)\n\t\treturn self.invModulos[pi]\n\n\tdef invFactorial(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate (n^(-1))!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.invFactorial_):\n\t\t\treturn self.invFactorial_[n]\n\t\tself.inv(n)\n\t\tnextArr = [0] * (n + 1 - len(self.invFactorial_))\n\t\tinitialI = len(self.invFactorial_)\n\t\tprev = self.invFactorial_[-1]\n\t\tp = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p\n\t\tself.invFactorial_ += nextArr\n\t\treturn self.invFactorial_[n]\n\nclass Combination:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorial = Factorial(MOD)\n\n\tdef ncr(self, n, k):\n\t\tif k < 0 or n < k:\n\t\t\treturn 0\n\t\tk = min(k, n - k)\n\t\tf = self.factorial\n\t\treturn f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD\nn = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tfor i in range(2, 5):\n\t\tprint(1, i)\n\tfor i in range(5, n + 1):\n\t\tprint(2, i)\nfor i in range(2, n + 1):\n\tprint(1, i)\n", "n = int(input())\nif n < 6:\n\tprint('-1')\nelse:\n\tres = []\n\tfor i in range(0, n - 1):\n\t\tif i % 2 == 0:\n\t\t\tfirst = '1'\n\t\telse:\n\t\t\tfirst = '2'\n\t\tres.append('%s %s' % (first, str(i + 2)))\n\tprint('\\n'.join(res))\nfor i in range(0, n - 1):\n\tprint('1 %s' % str(i + 2))\n", "import sys\nimport math\nimport collections\ndy = [1, 0, -1, 0]\ndx = [0, 1, 0, -1]\nr = sys.stdin.readline\nN = int(r())\nif N >= 6:\n\tprint(1, 2)\n\tfor i in range(3, N + 1):\n\t\tif i % 2 == 1:\n\t\t\tprint(1, i)\n\t\telse:\n\t\t\tprint(2, i)\nelse:\n\tprint(-1)\nfor i in range(1, N):\n\tprint(i, i + 1)\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tprint('1 2')\n\tprint('1 3')\n\tprint('1 4')\n\tfor k in range(5, n + 1):\n\t\tprint('2 ' + str(k))\nfor m in range(1, n):\n\tprint(str(m) + ' ' + str(m + 1))\n", "import os\nimport sys\nfrom math import *\nfrom collections import *\nfrom fractions import *\nfrom bisect import *\nfrom heapq import *\nfrom io import BytesIO, IOBase\n\ndef vsInput():\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nALPHA = 'abcdefghijklmnopqrstuvwxyz'\nMOD = 1000000007\n\ndef value():\n\treturn tuple(map(int, input().split()))\n\ndef array():\n\treturn [int(i) for i in input().split()]\n\ndef Int():\n\treturn int(input())\n\ndef Str():\n\treturn input()\n\ndef arrayS():\n\treturn [i for i in input().split()]\nn = Int()\nif n <= 5:\n\tprint(-1)\nelse:\n\tprint(1, 2)\n\tprint(1, 3)\n\tprint(1, 4)\n\tfor i in range(5, n + 1):\n\t\tprint(2, i)\nfor i in range(2, n + 1):\n\tprint(1, i)\n", "s = input()\nn = int(s)\noutput = []\nif n > 5:\n\toutput.append('1 2')\n\tfor i in range(3, (n + 1) // 2 + 2):\n\t\toutput.append('1 {}'.format(i))\n\tfor i in range((n + 1) // 2 + 2, n + 1):\n\t\toutput.append('2 {}'.format(i))\nelse:\n\toutput.append('-1')\nfor i in range(2, n + 1):\n\toutput.append('1 {}'.format(i))\nprint('\\n'.join(output))\n", "n = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tprint('1 2\\n2 3\\n2 4\\n4 5\\n4 6')\n\tfor i in range(0, (n - 6) // 2 * 2, 2):\n\t\tprint(1, i + 7)\n\t\tprint(i + 7, i + 8)\n\tif n % 2 == 1:\n\t\tprint(2, n)\nfor i in range(n - 1):\n\tprint(i + 1, i + 2)\n", "def wr(n):\n\tif n <= 5:\n\t\tprint(-1)\n\t\treturn\n\tprint(1, 2)\n\tprint(2, 3)\n\tprint(2, 4)\n\tprint(5, 1)\n\tprint(6, 1)\n\tx = 7\n\twhile x <= n:\n\t\tprint(1, x)\n\t\tx += 1\n\ndef cr(n):\n\tx = 2\n\twhile x <= n:\n\t\tprint(1, x)\n\t\tx += 1\nn = int(input())\nwr(n)\ncr(n)\n", "import sys\ninput = sys.stdin.readline\nfrom collections import defaultdict as dc\nfrom collections import Counter\nfrom bisect import bisect_right, bisect_left\nimport math\nfrom operator import itemgetter\nfrom heapq import heapify, heappop, heappush\nfrom queue import PriorityQueue as pq\nn = int(input())\nif n <= 5:\n\tprint(-1)\nelse:\n\tfor i in range(2, 5):\n\t\tprint(1, i)\n\tfor i in range(5, n + 1):\n\t\tprint(2, i)\nfor i in range(2, n + 1):\n\tprint(1, i)\n", "import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools\nimport sys\nimport random\nimport collections\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef f(n):\n\tif n <= 5:\n\t\tprint(-1)\n\t\treturn\n\tprint(1, 2)\n\tprint(1, 3)\n\tprint(1, 4)\n\tprint(2, 5)\n\tfor u in range(6, n + 1):\n\t\tprint(2, u)\n\treturn\nn = int(input())\nf(n)\nfor u in range(1, n):\n\tprint(u, u + 1)\n", "n = int(input())\nif n < 6:\n\tprint(-1)\n\t[print(1, i) for i in range(2, n + 1)]\n\texit()\n[print(1, i) for i in range(2, 5)]\n[print(2, i) for i in range(5, n + 1)]\n[print(1, i) for i in range(2, n + 1)]\n", "def ii():\n\treturn int(input())\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(mi())\nn = ii()\nif n < 6:\n\tprint(-1)\nelse:\n\tt = ['1 2', '1 3', '1 4', '2 5', '2 6']\n\tfor i in range(7, n + 1):\n\t\tt.append('1 ' + str(i))\n\tprint('\\n'.join(t))\nt = []\nfor i in range(2, n + 1):\n\tt.append('1 ' + str(i))\nprint('\\n'.join(t))\n", "n = int(input())\n\ndef print_correct(n):\n\tfor i in range(2, n + 1):\n\t\tprint('1 ' + str(i))\n\ndef print_incorrect(n):\n\tif n >= 6:\n\t\tprint('1 2')\n\t\tprint('2 3')\n\t\tprint('2 4')\n\t\tfor i in range(5, n + 1):\n\t\t\tprint('1 ' + str(i))\n\telse:\n\t\tprint('-1')\nprint_incorrect(n)\nprint_correct(n)\n", "import sys\ninput = sys.stdin.readline\nn = int(input())\nif n < 6:\n\tprint(-1)\nelse:\n\tl = []\n\to = []\n\tx = (3 + n) // 2\n\tfor i in range(3, x + 1):\n\t\tl.append((1, i))\n\tfor i in range(x + 1, n + 1):\n\t\to.append((2, i))\n\tsys.stdout.write('1' + ' ' + '2' + '\\n')\n\tfor x in l:\n\t\tsys.stdout.write(str(x[0]) + ' ' + str(x[1]) + '\\n')\n\tfor x in o:\n\t\tsys.stdout.write(str(x[0]) + ' ' + str(x[1]) + '\\n')\nsys.stdout.write('1' + ' ' + '2' + '\\n')\np = 2\nfor i in range(3, n + 1):\n\tsys.stdout.write(str(p) + ' ' + str(i) + '\\n')\n\tp = i\n", "import math\nimport heapq\nfrom queue import Queue\n\ndef main(n):\n\tif n < 6:\n\t\tprint(-1)\n\telse:\n\t\tprint(1, 2)\n\t\tprint(2, 3)\n\t\tprint(2, 4)\n\t\tprint(4, 5)\n\t\tprint(4, 6)\n\t\ta = 7\n\t\twhile a <= n:\n\t\t\tprint(2, a)\n\t\t\ta += 1\n\ta = 2\n\twhile a <= n:\n\t\tprint(1, a)\n\t\ta += 1\n\treturn\nn = int(input())\nmain(n)\n", "import sys\nimport math\ninput = sys.stdin.readline\n\ndef inp():\n\treturn int(input())\n\ndef inara():\n\treturn list(map(int, input().split()))\n\ndef insr():\n\ts = input()\n\treturn list(s[:len(s) - 1])\n\ndef invr():\n\treturn map(int, input().split())\nn = inp()\nif n <= 5:\n\tprint(-1)\nelse:\n\tfor i in range(2, 5):\n\t\tprint(str(1) + ' ' + str(i))\n\tfor i in range(5, n + 1):\n\t\tprint(str(2) + ' ' + str(i))\nfor i in range(2, n + 1):\n\tprint(str(1) + ' ' + str(i))\n"]

difficulty: MEDIUM

source: codeforces

raw_problem:
C. Mahmoud and Ehab and the wrong algorithm

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Mahmoud was trying to solve the vertex cover problem on trees. The problem statement is:

Given an undirected tree consisting of n nodes, find the minimum number of vertices that cover all the edges. Formally, we need to find a set of vertices such that for each edge (u, v) that belongs to the tree, either u is in the set, or v is in the set, or both are in the set. Mahmoud has found the following algorithm:

 Root the tree at node 1.

 Count the number of nodes at an even depth. Let it be evenCnt.

 Count the number of nodes at an odd depth. Let it be oddCnt.

 The answer is the minimum between evenCnt and oddCnt.

The depth of a node in a tree is the number of edges in the shortest path between this node and the root. The depth of the root is 0.

Ehab told Mahmoud that this algorithm is wrong, but he didn't believe because he had tested his algorithm against many trees and it worked, so Ehab asked you to find 2 trees consisting of n nodes. The algorithm should find an incorrect answer for the first tree and a correct answer for the second one.

Input

The only line contains an integer n (2 ≤ n ≤ 105), the number of nodes in the desired trees.

Output

The output should consist of 2 independent sections, each containing a tree. The algorithm should find an incorrect answer for the tree in the first section and a correct answer for the tree in the second. If a tree doesn't exist for some section, output "-1" (without quotes) for that section only.

If the answer for a section exists, it should contain n - 1 lines, each containing 2 space-separated integers u and v (1 ≤ u, v ≤ n), which means that there's an undirected edge between node u and node v. If the given graph isn't a tree or it doesn't follow the format, you'll receive wrong answer verdict.

If there are multiple answers, you can print any of them.

Examples

Input

2

Output

-1
1 2

Input

8

Output

1 2
1 3
2 4
2 5
3 6
4 7
4 8
1 2
1 3
2 4
2 5
2 6
3 7
6 8

Note

In the first sample, there is only 1 tree with 2 nodes (node 1 connected to node 2). The algorithm will produce a correct answer in it so we printed  - 1 in the first section, but notice that we printed this tree in the second section.

In the second sample:

In the first tree, the algorithm will find an answer with 4 nodes, while there exists an answer with 3 nodes like this:  In the second tree, the algorithm will find an answer with 3 nodes which is correct:

question:
Mahmoud was trying to solve the vertex cover problem on trees. The problem statement is:
Given an undirected tree consisting of n nodes, find the minimum number of vertices that cover all the edges. Formally, we need to find a set of vertices such that for each edge (u, v) that belongs to the tree, either u is in the set, or v is in the set, or both are in the set. Mahmoud has found the following algorithm:
 -  Root the tree at node 1. -  Count the number of nodes at an even depth. Let it be evenCnt. -  Count the number of nodes at an odd depth. Let it be oddCnt. -  The answer is the minimum between evenCnt and oddCnt. The depth of a node in a tree is the number of edges in the shortest path between this node and the root. The depth of the root is 0.
Ehab told Mahmoud that this algorithm is wrong, but he didn't believe because he had tested his algorithm against many trees and it worked, so Ehab asked you to find 2 trees consisting of n nodes. The algorithm should find an incorrect answer for the first tree and a correct answer for the second one.

Input
The only line contains an integer n (2 ≤ n ≤ 10^{5}), the number of nodes in the desired trees.

Output
The output should consist of 2 independent sections, each containing a tree. The algorithm should find an incorrect answer for the tree in the first section and a correct answer for the tree in the second. If a tree doesn't exist for some section, output "-1" (without quotes) for that section only.
If the answer for a section exists, it should contain n - 1 lines, each containing 2 space-separated integers u and v (1 ≤ u, v ≤ n), which means that there's an undirected edge between node u and node v. If the given graph isn't a tree or it doesn't follow the format, you'll receive wrong answer verdict.
If there are multiple answers, you can print any of them.

Examples
Input
2

Output
-1
1 2

Input
8

Output
1 2
1 3
2 4
2 5
3 6
4 7
4 8
1 2
1 3
2 4
2 5
2 6
3 7
6 8

Note
In the first sample, there is only 1 tree with 2 nodes (node 1 connected to node 2). The algorithm will produce a correct answer in it so we printed  - 1 in the first section, but notice that we printed this tree in the second section.
In the second sample:
In the first tree, the algorithm will find an answer with 4 nodes, while there exists an answer with 3 nodes like this: ![image](1.png) In the second tree, the algorithm will find an answer with 3 nodes which is correct: ![image](2.png)

tags: ['Tree algorithms', 'Constructive algorithms']

Expected Time Complexity: O(N)

image_tags: Tree Tree

data_split: test


I. Falling Blocks

problem_index: I

time_limit: 3 seconds

memory_limit: 512 megabytes

source: codeforces

raw_problem:
I. Falling Blocks

time limit per test
3 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Recently, Polycarp has invented a new mobile game with falling blocks.

In the game, $$$n$$$ blocks are falling down, one at a time, towards a flat surface with length $$$d$$$ units. Each block can be represented as a rectangle with coordinates from $$$l_i$$$ to $$$r_i$$$ and unit height, dropped downwards from very high up. A block falls until it comes in contact with the flat surface or any other block. Let's define that block $$$a$$$ covers block $$$b$$$ if $$$l_a \le l_b \le r_b \le r_a$$$.

Consider what happens when a new block $$$i$$$ falls. If the new (upper) block $$$i$$$ comes in contact with any block $$$j$$$ such that block $$$i$$$ does not cover block $$$j$$$, block $$$i$$$ will stick to block $$$j$$$, and no blocks will disappear. Otherwise, all blocks that block $$$i$$$ covers and is in contact with will be vaporized, and block $$$i$$$ will continue falling with the ability to vaporize lower blocks.

For example, consider what happens when three blocks $$$(1,2)$$$, $$$(2,3)$$$ and $$$(1,3)$$$ fall, in that order. The first block will stick to the flat surface. Then, the second block will stick to the first block. Finally, the third block will vaporize the second block, keep falling, vaporize the first block, and stick to the flat surface.
  Here is a graphic for the first example.
After each block falls, help Polycarp determine how many blocks will remain!

Input

The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \le n, d \le 10^5$$$)  — the number of falling blocks and the length of the flat surface.

The $$$i$$$-th of the following $$$n$$$ lines contains integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le d$$$)  — the coordinates of the $$$i$$$-th block.

Output

Output $$$n$$$ integers. The $$$i$$$-th integer should be the number of blocks that will be left after the $$$i$$$-th block falls.

Examples

Input

3 3
1 2
2 3
1 3

Output

1
2
1

Input

8 6
1 2
3 3
2 3
1 3
2 4
3 6
1 5
1 5

Output

1
2
3
1
2
3
4
4

Note

The first example is explained above.

In the second example, this is what happens after each block falls:

 Block $$$1$$$ will stick to the flat surface.

 Block $$$2$$$ will stick to the flat surface.

 Block $$$3$$$ will stick to blocks $$$1$$$ and $$$2$$$. Note that block $$$3$$$ will not vaporize block $$$2$$$ because it does not cover block $$$1$$$ and is in contact with it.

 Block $$$4$$$ will vaporize all the blocks and stick to the flat surface.

 Block $$$5$$$ will stick to block $$$4$$$

 Block $$$6$$$ will stick to block $$$5$$$.

 Block $$$7$$$ will stick to block $$$6$$$. Note that no blocks are vaporized because although block $$$7$$$ covers block $$$4$$$ and block $$$5$$$, they never come in contact.

 Block $$$8$$$ vaporizes block $$$7$$$ and sticks to block $$$6$$$.

question:
Recently, Polycarp has invented a new mobile game with falling blocks.
In the game, $$$n$$$ blocks are falling down, one at a time, towards a flat surface with length $$$d$$$ units. Each block can be represented as a rectangle with coordinates from $$$l_i$$$ to $$$r_i$$$ and unit height, dropped downwards from very high up. A block falls until it comes in contact with the flat surface or any other block. Let's define that block $$$a$$$ covers block $$$b$$$ if $$$l_a \le l_b \le r_b \le r_a$$$.
Consider what happens when a new block $$$i$$$ falls. If the new (upper) block $$$i$$$ comes in contact with any block $$$j$$$ such that block $$$i$$$ does not cover block $$$j$$$, block $$$i$$$ will stick to block $$$j$$$, and no blocks will disappear. Otherwise, all blocks that block $$$i$$$ covers and is in contact with will be vaporized, and block $$$i$$$ will continue falling with the ability to vaporize lower blocks.
For example, consider what happens when three blocks $$$(1,2)$$$, $$$(2,3)$$$ and $$$(1,3)$$$ fall, in that order. The first block will stick to the flat surface. Then, the second block will stick to the first block. Finally, the third block will vaporize the second block, keep falling, vaporize the first block, and stick to the flat surface.
 ![image](1.png) Here is a graphic for the first example. After each block falls, help Polycarp determine how many blocks will remain!

Input
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \le n, d \le 10^5$$$)  — the number of falling blocks and the length of the flat surface.
The $$$i$$$-th of the following $$$n$$$ lines contains integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le d$$$)  — the coordinates of the $$$i$$$-th block.

Output
Output $$$n$$$ integers. The $$$i$$$-th integer should be the number of blocks that will be left after the $$$i$$$-th block falls.

Examples
Input
3 3
1 2
2 3
1 3

Output
1
2
1

Input
8 6
1 2
3 3
2 3
1 3
2 4
3 6
1 5
1 5

Output
1
2
3
1
2
3
4
4

Note
The first example is explained above.
In the second example, this is what happens after each block falls:
 -  Block $$$1$$$ will stick to the flat surface. -  Block $$$2$$$ will stick to the flat surface. -  Block $$$3$$$ will stick to blocks $$$1$$$ and $$$2$$$. Note that block $$$3$$$ will not vaporize block $$$2$$$ because it does not cover block $$$1$$$ and is in contact with it. -  Block $$$4$$$ will vaporize all the blocks and stick to the flat surface. -  Block $$$5$$$ will stick to block $$$4$$$ -  Block $$$6$$$ will stick to block $$$5$$$. -  Block $$$7$$$ will stick to block $$$6$$$. Note that no blocks are vaporized because although block $$$7$$$ covers block $$$4$$$ and block $$$5$$$, they never come in contact. -  Block $$$8$$$ vaporizes block $$$7$$$ and sticks to block $$$6$$$.

skill_types: ['Data structures']

data_split: test