Universal Cup Judging System

Universal Cup

حد الوقت: 1.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Description

Using only resistors with resistance $1\,[\Omega]$, construct a resistor with resistance $\sqrt{D}\,[\Omega]$.

You are given a positive integer $D$. Construct one connected undirected graph satisfying all of the following conditions. Under the constraints of this problem, it can be proven that such a graph always exists.

  • The number of vertices $N$ is between $2$ and $300$ ($2$ and $300$ inclusive), and each vertex has a distinct label from $1$ to $N$.
  • The number of edges $M$ is at most $300$, and self-loops and multiple edges are allowed.
  • The "effective resistance from vertex $1$ to vertex $N$", defined as below, is within an absolute error of $\pm 10^{-6}$ from $\sqrt{D}$.

Let $G$ be a connected undirected graph with $n$ vertices and $m$ edges ($n \ge 2$), and suppose that the $j$-th edge connects vertices $a_j, b_j$. Consider assigning a real number $V_i$ ($i = 1, 2, \dots, n$) to each vertex of graph $G$, and a real number $I_j$ ($j = 1, 2, \dots, m$) to each edge, so that all of the following equations are satisfied:

  • $I_j = V_{a_j} - V_{b_j} \quad (j = 1, 2, \dots, m)$
  • $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0 \quad (i = 2, 3, \dots, n - 1)$
  • $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

It can be proven that such an assignment always exists, and furthermore that the value of $V_1 - V_n$ is uniquely determined. We define this value as the "effective resistance from vertex $1$ to vertex $n$".

Input

The input consists of a single positive integer $D$. ($1 \le D \le 5000$)

Output

On the first line, print the number of vertices $N$ and the number of edges $M$ of the constructed graph, in this order, separated by spaces.

On each of the following $M$ lines, the $i$-th line ($i = 1, 2, \dots, M$) should contain the two endpoints of the $i$-th edge, separated by a space.

If there are multiple graphs satisfying the conditions, any one of them may be printed.

Examples

Input 1

1

Output 1

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

Note

The following is an illustration of the output for Example 1.

problem_17723_8.png

That the effective resistance from vertex $1$ to vertex $n$ is $1\,[\Omega]$ can be explained as follows:

  • Since all resistors have resistance $1\,[\Omega]$, and by symmetry the potentials at vertices $2$ and $3$ are equal, the resistor between them can be treated as if it does not exist.
  • As a result, the circuit reduces to two branches in parallel, each branch consisting of two $1\,[\Omega]$ resistors in series.
  • The effective resistance of two $1\,[\Omega]$ resistors in series is $2\,[\Omega]$, and the effective resistance of two $2\,[\Omega]$ resistors in parallel is $1\,[\Omega]$.

The following output is also considered correct:

2 1
1 2

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1532EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.