/kloc-in the 0/8th century, there was a beautiful town in Europe-Konigsberg, where there were seven bridges. As shown in figure 1, there are two bridges connecting the small island A in the river with the left bank B and the right bank C of the river, and another bridge connecting the land D between the two tributaries of the river with A, B and C respectively. At that time, there was a question among the residents of Konigsberg: How can a person walk over seven bridges at a time, each bridge only once, and finally return to the starting point? Everyone tries to find the answer to the question, but no one can solve it.

The problem of the Seven Bridges has attracted the attention of the famous mathematician Euler (1707— 1783). He classified the specific layout of the seven bridges as a simple figure as shown in Figure 2, so the problem of the seven bridges became a problem: how can we draw this simple figure one by one from a certain point of A, B, C and D (that is, the lines of A, B, C, D, E, F and G can only be drawn once) and finally return to the starting point? The conclusion of Euler's research is that Figure 2 is a figure that cannot be drawn with one stroke. In other words, there is no solution to the seven bridges problem. How did this conclusion come about? Please see the analysis below.

If we start from a certain point and draw a certain figure with one stroke and end at a certain point, then every time the brush passes through a point other than the starting point and the ending point, there is always a line drawn into the point and a line drawn at the point, so there are two lines connected to the point. If the brush passes n times, 2n lines are connected to the point. Therefore, all points in this graph except the starting point and the ending point are connected by even lines. If the starting point and the ending point coincide, then this point is also connected with even lines; If the starting point and the ending point are two different points, then these two points are points connected by odd lines. To sum up, all the points in a drawing are connected by even lines, or only two points are connected by odd lines.

In Figure 2, point A is connected by five lines, point B, point C and point D are connected by three lines respectively, and four points in the figure are connected by odd lines, so no matter whether the starting point and the ending point are required to coincide or not, the figure can not be drawn with one stroke.

1736, Euler gave an academic report at St. Petersburg Academy of Sciences. In the report, he proved the above conclusion. Later, he gave a criterion to judge whether any figure can be drawn with one stroke, that is, euler theorem. In order to introduce this theorem, let's take a look at the following preliminary knowledge:

A graph consisting of a finite number of lines is called a network, in which each line needs two different endpoints. These lines are called arcs of the network, and the endpoints of the arcs are called vertices of the network. For example, Figure 2 is a network. A, B, C, D, E, F and G are its seven arcs, and A, B, C and D are its four vertices.

A series of arcs knotted with each other in the network are called roads. If any two vertices in a network can be connected by a path, then the network is called connected; Otherwise it is called unconnected. For example, Figure 2 is a connected network; Figure 3 is a disconnected network, in which some vertices (such as A and D) have no routing connection.

The number of arcs with a vertex as the endpoint in the network is called the intersection number of the vertex. Vertices with odd bifurcation numbers are called odd vertices, and vertices with even bifurcation numbers are called even vertices.

Euler theorem is introduced below.

Euler theorem If a network is connected and the number of odd vertices is equal to 0 or 2, then it can be drawn with one stroke; Otherwise, you can't draw a stroke.

Euler theorem can easily judge whether a simple figure can be drawn with one stroke.