ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem A
Secret of Chocolate Poles
Time Limit: 1 second
Wendy, the master of a chocolate shop, is thinking of displaying poles of chocolate disks in the
showcase. She can use three kinds of chocolate disks: white thin disks, dark thin disks, anddark thick disks. The thin disks are 1 cm thick, and the thick disks are k cm thick. Disks will
be piled in glass cylinders.
Each pole should satisfy the following conditions for her secret mission, which we cannot tell.
• A pole should consist of at least one disk.
• The total thickness of disks in a pole should be less than or equal to l cm.
• The top disk and the bottom disk of a pole should be dark.
• A disk directly upon a white disk should be dark and vice versa.
As examples, six side views of poles are drawn in Figure A.1. These are the only possible sideviews she can make when l = 5 and k = 3.

Figure A.1. Six chocolate poles corresponding to Sample Input 1
Your task is to count the number of distinct side views she can make for given l and k to help
her accomplish her secret mission.

1

Input
The input consists of a single test case in the following format.
lkHere, the maximum possible total thickness of disks in a pole is l cm, and the thickness of the
thick disks is k cm. l and k are integers satisfying 1 ≤ l ≤ 100 and 2 ≤ k ≤ 10.

OutputOutput the number of possible distinct patterns.
Sample Input 1

Sample Output 1

5 3

6Sample Input 2

Sample Output 2

9 10

5

Sample Input 3

Sample Output 3

10 10

6

Sample Input 4

Sample Output 4

20 5

86

Sample Input 5

Sample Output 5

100 23626169232670

2

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem B
Parallel Lines
Time Limit: 10 seconds
Given an even number of distinct planar points, consider coupling all of the points into pairs.
All the possible couplings are to be considered as long as all the given points are coupled to one
and only one other point.
When lines are drawn connecting the two points of all the coupled point pairs, some of thedrawn lines can be parallel to some others. Your task is to find the maximum number of parallel
line pairs considering all the possible couplings of the points.
For the case given in the first sample input with four points, there are three patterns of point
couplings as shown in Figure B.1. The numbers of parallel line pairs are 0, 0, and 1, from theleft. So the maximum is 1.

Figure B.1. All three possible couplings for Sample Input 1

For the case given in the second sample input with eight points, the points can be coupled asshown in Figure B.2. With such a point pairing, all four lines are parallel to one another. In
other words, the six line pairs (L1 , L2 ), (L1 , L3 ), (L1 , L4 ), (L2 , L3 ), (L2 , L4 ) and (L3 , L4 ) are
parallel. So the maximum number of parallel line pairs, in this case, is 6.

Input
The input consists of a single test case of the following format.
m
x1 y1
..
.
xm ym
3

Figure B.2. Maximizing the number of parallel line pairs for Sample Input 2

The first line contains an even integer m, which is the number of points (2 ≤ m ≤ 16). Each of
the following m lines gives the coordinates of a point. Integers xi and yi (−1000 ≤ xi ≤ 1000,−1000 ≤ yi ≤ 1000) in the i-th line of them give the x- and y-coordinates, respectively, of thei-th point.
The positions of points are all different, that is, xi 6= xj or yi 6= yj holds for all i 6= j. Furthermore, No three points lie on a single line.

OutputOutput the maximum possible number of parallel line pairs stated above, in one line.
Sample Input 1

Sample Output 1

4
0 0
1 1
0 2
2 4

1

4

Sample Input 2

Sample Output 2

8
0 0
0 5
2 2
2 7
3 -2
5 0
4 -2
8 2

6

Sample Input 3

Sample Output 3

6
0 0
0 5
3 -2
3 5
5 0
5 7

3

Sample Input 4

Sample Output 4

2-1000 1000
1000 -10000Sample Input 5

Sample Output 5

16
327 449-509 761-553 515
360 948
147 877-694 468
241 320463 -753-206 -991
473 -738-156 -916-215 54-112 -476-452 780-18 -335-146 7712

5

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem C
Medical Checkup
Time Limit: 2 seconds
Students of the university have to go for a medical checkup, consisting of lots of checkup items,
numbered 1, 2, 3, and so on.
Students are now forming a long queue, waiting for the checkup to start. Students are also
numbered 1, 2, 3, and so on, from the top of the queue. They have to undergo checkup items in
the order of the item numbers, not skipping any of them nor changing the order. The order ofstudents should not be changed either.
Multiple checkup items can be carried out in parallel, but each item can be carried out for only
one student at a time. Students have to wait in queues of their next checkup items until all theothers before them finish.
Each of the students is associated with an integer value called health condition. For a studentwith the health condition h, it takes h minutes to finish each of the checkup items. You may
assume that no interval is needed between two students on the same checkup item or two checkup
items for a single student.
Your task is to find the items students are being checked up or waiting for at a specified time t.

Input
The input consists of a single test case in the following format.
nt
h1
..
.
hn
n and t are integers. n is the number of the students (1 ≤ n ≤ 105 ). t specifies the timeof our concern (0 ≤ t ≤ 109 ). For each i, the integer hi is the health condition of student i(1 ≤ hi ≤ 109 ).

OutputOutput n lines each containing a single integer. The i-th line should contain the checkup item
number of the item which the student i is being checked up or is waiting for, at (t + 0.5) minutes
after the checkup starts. You may assume that all the students are yet to finish some of thecheckup items at that moment.
6

Sample Input 1

Sample Output 1

3 20
5
7
3

5
3
2

Sample Input 2

Sample Output 2

5 1000000000
5553
2186
3472
2605
1790

180083
180083
180082
180082
180082

7

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem D
Making Perimeter of the Convex Hull Shortest
Time Limit: 10 seconds
The convex hull of a set of three or more planar points is, when not all of them are on one line,
the convex polygon with the smallest area that has all the points of the set on its boundary orin its inside. Your task is, given positions of the points of a set, to find how much shorter the
perimeter of the convex hull can be made by excluding two points from the set.
The figures below correspond to the three cases given as Sample Input 1 to 3. Encircled points
are excluded to make the shortest convex hull depicted as thick dashed lines.

Sample Input 1

Sample Input 2

Sample Input 3

Input
The input consists of a single test case in the following format.
n
x 1 y1..
.
x n ynHere, n is the number of points in the set satisfying 5 ≤ n ≤ 105 . For each i, (xi , yi ) gives thecoordinates of the position of the i-th point in the set. xi and yi are integers between −106 and
106 , inclusive. All the points in the set are distinct, that is, xj 6= xk or yj 6= yk holds whenj 6= k. It is guaranteed that no single line goes through n − 2 or more points in the set.
8

Output
Output the difference of the perimeter of the convex hull of the original set and the shortest of
the perimeters of the convex hulls of the subsets with two points excluded from the original set.
The output should not have an error greater than 10−4 .
Sample Input 1

Sample Output 1

10-53 62-19 58-11 11-9 -22
45 -7
37 -3947 -58-2 41-37 1013 4272.96316928

Sample Input 2

Sample Output 2

10-53 62-19 58-11 11-9 -22
45 -7
43 -4747 -58-2 41-37 1013 4262.62947992

Sample Input 3

Sample Output 3

10-53 62-35 47-11 11-9 -22
45 -7
43 -4747 -58-2 41-37 1013 4261.58166534

9

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem E
Black or WhiteTime Limit: 2 seconds
Here lies a row of a number of bricks each painted either black or white. With a single stroke ofyour brush, you can overpaint a part of the row of bricks at once with either black or white paint.
Using white paint, all the black bricks in the painted part become white while originally whitebricks remain white; with black paint, white bricks become black and black ones remain black.
The number of bricks painted in one stroke, however, is limited because your brush cannot holdtoo much paint at a time. For each brush stroke, you can paint any part of the row with any
number of bricks up to the limit.
In the first case of the sample input, the initial colors of four bricks are black, white, white, andblack. You can repaint them to white, black, black, and white with two strokes: the first stroke
paints all four bricks white and the second stroke paints two bricks in the middle black.
Your task is to calculate the minimum number of brush strokes needed to change the brick colors
as specified. Never mind the cost of the paints.

Input
The input consists of a single test case formatted as follows.
nkst
The first line contains two integers n and k (1 ≤ k ≤ n ≤ 500 000). n is the number of bricks
in the row and k is the maximum number of bricks painted in a single stroke. The second line
contains a string s of n characters, which indicates the initial colors of the bricks. The third line
contains another string t of n characters, which indicates the desired colors of the bricks. All
the characters in both s and t are either B or W meaning black and white, respectively.

OutputOutput the minimum number of brush strokes required to repaint the bricks into the desiredcolors.
Sample Input 1

Sample Output 1

4 4
BWWB
WBBW

2

10

Sample Input 2

Sample Output 2

4 3
BWWB
WBBW

3

Sample Input 3

Sample Output 3

4 3
BWWW
BWWW

0

Sample Input 4

Sample Output 4

7 1
BBWBWBWWBBWWBB

4

11

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem F
Pizza Delivery
Time Limit: 2 seconds
Alyssa is a college student, living in New Tsukuba City. All the streets in the city are oneway. A new social experiment starting tomorrow is on alternative traffic regulation reversing
the one-way directions of street sections. Reversals will be on one single street section between
two adjacent intersections for each day; the directions of all the other sections will not change,
and the reversal will be canceled on the next day.
Alyssa orders a piece of pizza everyday from the same pizzeria. The pizza is delivered along theshortest route from the intersection with the pizzeria to the intersection with Alyssa’s house.
Altering the traffic regulation may change the shortest route. Please tell Alyssa how the social
experiment will affect the pizza delivery route.

Input
The input consists of a single test case in the following format.
nm
a1 b1 c1..
.
am bm cm
The first line contains two integers, n, the number of intersections, and m, the number of street
sections in New Tsukuba City (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000). The intersections arenumbered 1 through n and the street sections are numbered 1 through m.
The following m lines contain the information about the street sections, each with three integers
ai , bi , and ci (1 ≤ ai ≤ n, 1 ≤ bi ≤ n, ai 6= bi , 1 ≤ ci ≤ 100 000). They mean that the street
section numbered i connects two intersections with the one-way direction from ai to bi , which
will be reversed on the i-th day. The street section has the length of ci . Note that there may be
more than one street section connecting the same pair of intersections.
The pizzeria is on the intersection 1 and Alyssa’s house is on the intersection 2. It is guaranteedthat at least one route exists from the pizzeria to Alyssa’s before the social experiment starts.

OutputThe output should contain m lines. The i-th line should be
12• HAPPY if the shortest route on the i-th day will become shorter,• SOSO if the length of the shortest route on the i-th day will not change, and• SAD if the shortest route on the i-th day will be longer or if there will be no route fromthe pizzeria to Alyssa’s house.
Alyssa doesn’t mind whether the delivery bike can go back to the pizzeria or not.
Sample Input 1

Sample Output 1

4 5
1 3 5
3 4 6
4 2 7
2 1 182 3 12

SAD
SAD
SAD
SOSO
HAPPY

Sample Input 2

Sample Output 2

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

SOSO
SAD
SOSO
SAD
SOSO

Sample Input 3

Sample Output 3

10 14
1 7 9
1 8 3
2 8 4
2 6 11
3 7 8
3 4 4
3 2 1
3 2 7
4 8 4
5 6 115 8 126 10 6
7 10 8
8 3 6

SOSO
SAD
HAPPY
SOSO
SOSO
SOSO
SAD
SOSO
SOSO
SOSO
SOSO
SOSO
SOSO
SAD

13

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem G
Rendezvous on a TetrahedronTime Limit: 1 second
One day, you found two worms P and Q crawling on the surface of a regular tetrahedron withfour vertices A, B, C, and D. Both worms started from the vertex A, went straight ahead, andstopped crawling after a while.
When a worm reached one of the edges of the tetrahedron, it moved on to the adjacent face andkept going without changing the angle to the crossed edge (Figure G.1).
Write a program which tells whether or not P and Q were on the same face of the tetrahedronwhen they stopped crawling.
You may assume that each of the worms is a point without length, area, or volume.

Figure G.1. Crossing an edge
Incidentally, lengths of the two trails the worms left on the tetrahedron were exact integral multiples of the unit length. Here, the unit length is the edge length of the tetrahedron. Each trail ismore than 0.001 unit distant from any vertices, except for its start point and its neighborhood.
This means that worms have crossed at least one edge. Both worms stopped at positions morethan 0.001 unit distant from any of the edges.
The initial crawling direction of a worm is specified by two items: the edge XY which is thefirst edge the worm encountered after its start, and the angle d between the edge AX and the14direction of the worm, in degrees.
A

C
P

B
Q

D
Figure G.2. Trails of the worms corresponding to Sample Input 1

Figure G.2 shows the case of Sample Input 1. In this case, P went over the edge CD and stopped
on the face opposite to the vertex A, while Q went over the edge DB and also stopped on thesame face.

Input
The input consists of a single test case, formatted as follows.
XP YP dP lP
XQ YQ dQ lQ
XW YW (W = P, Q) is the first edge the worm W crossed after its start. XW YW is one of BC,
CD or DB.
An integer dW (1 ≤ dW ≤ 59) is the angle in degrees between edge AXW and the initial directionof the worm W on the face 4AXW YW .
An integer lW (1 ≤ lW ≤ 20) is the length of the trail of worm W left on the surface, in unit
lengths.

15

Output
Output YES when and only when the two worms stopped on the same face of the tetrahedron.
Otherwise, output NO.
Sample Input 1

Sample Output 1

CD 30 1
DB 30 1YES

Sample Input 2

Sample Output 2

BC 1 1
DB 59 1YES

Sample Input 3

Sample Output 3

BC 29 20
BC 32 20

NO

16

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem H
Homework
Time Limit: 2 seconds
Taro is a student of Ibaraki College of Prominent Computing. In this semester, he takes twocourses, mathematics and informatics. After each class, the teacher may assign homework. Taro
may be given multiple assignments in a single class, and each assignment may have a different
deadline. Each assignment has a unique ID number.
Everyday after school, Taro completes at most one assignment as follows. First, he decides whichcourse’s homework to do at random by flipping a coin. Let S be the set of all the unfinishedassignments of the chosen course whose deadline has not yet passed. If S is empty, he plays avideo game without doing any homework on that day even if there are unfinished assignments of
the other course. Otherwise, with T ⊆ S being the set of assignments with the nearest deadline
among S, he completes the one with the smallest assignment ID among T .
The number of assignments Taro will complete until the end of the semester depends on the
result of coin flips. Given the schedule of homework assignments, your task is to compute themaximum and the minimum numbers of assignments Taro will complete.

Input
The input consists of a single test case in the following format.
nm
s1 t1
..
.
sn tn
The first line contains two integers n and m satisfying 1 ≤ m < n ≤ 400. n denotes thetotal number of assignments in this semester, and m denotes the number of assignments ofthe mathematics course (so the number of assignments of the informatics course is n − m).
Each assignment has a unique ID from 1 to n; assignments with IDs 1 through m are thoseof the mathematics course, and the rest are of the informatics course. The next n lines show
the schedule of assignments. The i-th line of them contains two integers si and ti satisfying
1 ≤ si ≤ ti ≤ 400, which means that the assignment of ID i is given to Taro on the si -th day ofthe semester, and its deadline is the end of the ti -th day.

OutputIn the first line, print the maximum number of assignments Taro will complete. In the second
line, print the minimum number of assignments Taro will complete.
17

Sample Input 1

Sample Output 1

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

6
2

Sample Input 2

Sample Output 2

6 3
1 1
2 3
4 4
1 1
2 4
3 3

4
3

18

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem I
Starting a Scenic Railroad Service
Time Limit: 2 seconds
Jim, working for a railroad company, is responsible for planning a new tourist train service. He
is sure that the train route along a scenic valley will arise a big boom, but not quite sure how
big the boom will be.
A market survey was ordered and Jim has just received an estimated list of passengers’ travel
sections. Based on the list, he’d like to estimate the minimum number of train seats that meetsthe demand.
Providing as many seats as all of the passengers may cost unreasonably high. Assigning thesame seat to more than one passenger without overlapping travel sections may lead to a greatcost cutback.
Two different policies are considered on seat assignments. As the views from the train windows
depend on the seat positions, it would be better if passengers can choose a seat. One possible
policy (named ‘policy-1’) is to allow the passengers to choose an arbitrary seat among all theremaining seats when they make their reservations. As the order of reservations is unknown, all
the possible orders must be considered on counting the required number of seats.
The other policy (named ‘policy-2’) does not allow the passengers to choose their seats; the seat
assignments are decided by the railroad operator, not by the passengers, after all the reservations
are completed. This policy may reduce the number of the required seats considerably.
Your task is to let Jim know how different these two policies are by providing him a programthat computes the numbers of seats required under the two seat reservation policies.
Let us consider a case where there are four stations, S1, S2, S3, and S4, and four expectedpassengers p1 , p2 , p3 , and p4 with the travel list below.
passenger
p1
p2
p3
p4

from
S1
S2
S1
S3

to
S2
S3
S3
S4

The travel sections of p1 and p2 do not overlap, that of p3 overlaps those of p1 and p2 , and thatof p4 does not overlap those of any others.
Let’s check if two seats would suffice under the policy-1. If p1 books a seat first, either of thetwo seats can be chosen. If p2 books second, as the travel section does not overlap that of p1 ,19

the same seat can be booked, but the other seat may look more attractive to p2 . If p2 reservesa seat different from that of p1 , there will remain no available seats for p3 between S1 and S3(Figure I.1).
S1

S2

S3

(p1 )

seat A

S4
(p4 )

(p2 )

seat B(p3 )No seatFigure I.1. With two seatsWith three seats, p3 can find a seat with any seat reservation combinations by p1 and p2 . p4
can also book a seat for there are no other passengers between S3 and S4 (Figure I.2).
S1

S2

S3

(p1 )

seat A

S4
(p4 )

(p2 )

seat B(p3 )seat C

Figure I.2. With three seats
For this travel list, only three seats suffice considering all the possible reservation orders andseat preferences under the policy-1.
On the other hand, deciding the seat assignments after all the reservations are completed enables
a tight assignment with only two seats under the policy-2 (Figure I.3).
S1

S2

seat A(p1 )seat B

(p3 )

S3
(p2 )

S4
(p4 )

Figure I.3. Tight assignment to two seats

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

20

n
a1 b1
..
.
an bn
Here, the first line has an integer n, the number of the passengers in the estimated list ofpassengers’ travel sections (1 ≤ n ≤ 200 000). The stations are numbered starting from 1
in their order along the route. Each of the following n lines describes the travel for eachpassenger by two integers, the boarding and the alighting station numbers, ai and bi , respectively(1 ≤ ai < bi ≤ 100 000). Note that more than one passenger in the list may have the sameboarding and alighting stations.

OutputTwo integers s1 and s2 should be output in a line in this order, separated by a space. s1 and s2
are the numbers of seats required under the policy-1 and -2, respectively.
Sample Input 1

Sample Output 1

4
1 3
1 3
3 6
3 6

2 2

Sample Input 2

Sample Output 2

4
1 2
2 3
1 3
3 4

3 2

Sample Input 3

Sample Output 3

1084 302
275 327364 538
26 36429 386545 955715 965404 415903 942
150 402

6 5

21

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem J
String Puzzle
Time Limit: 2 seconds
Amazing Coding Magazine is popular among young programmers for its puzzle solving contests
offering catchy digital gadgets as the prizes. The magazine for programmers naturally encourages
the readers to solve the puzzles by writing programs. Let’s give it a try!
The puzzle in the latest issue is on deciding some of the letters in a string (the secret string,in what follows) based on a variety of hints. The figure below depicts an example of the given
hints.

The first hint is the number of letters in the secret string. In the example of the figure above, it
is nine, and the nine boxes correspond to nine letters. The letter positions (boxes) are numbered
starting from 1, from the left to the right.
The hints of the next kind simply tell the letters in the secret string at some specific positions.
In the example, the hints tell that the letters in the 3rd, 4th, 7th, and 9th boxes are C, I, C, andP, respectively.
The hints of the final kind are on duplicated substrings in the secret string. The bar immediately
below the boxes in the figure is partitioned into some sections corresponding to substrings of thesecret string. Each of the sections may be connected by a line running to the left with anotherbar also showing an extent of a substring. Each of the connected pairs indicates that substringsof the two extents are identical. One of this kind of hints in the example tells that the lettersin boxes 8 and 9 are identical to those in boxes 4 and 5, respectively. From this, you can easily
deduce that the substring is IP.
Note that, not necessarily all of the identical substring pairs in the secret string are given in thehints; some identical substring pairs may not be mentioned.
Note also that two extents of a pair may overlap each other. In the example, the two-letter
substring in boxes 2 and 3 is told to be identical to one in boxes 1 and 2, and these two extents
share the box 2.
22

In this example, you can decide letters at all the positions of the secret string, which are“CCCIPCCIP”. In general, the hints may not be enough to decide all the letters in the secretstring.
The answer of the puzzle should be letters at the specified positions of the secret string. Whenthe letter at the position specified cannot be decided with the given hints, the symbol ? should
be answered.

Input
The input consists of a single test case in the following format.
nabq
x1 c1
..
.
xa ca
y1 h1
..
.
yb hb
z1
..
.
zq
The first line contains four integers n, a, b, and q. n (1 ≤ n ≤ 109 ) is the length of thesecret string, a (0 ≤ a ≤ 1000) is the number of the hints on letters in specified positions, b(0 ≤ b ≤ 1000) is the number of the hints on duplicated substrings, and q (1 ≤ q ≤ 1000) is thenumber of positions asked.
The i-th line of the following a lines contains an integer xi and an uppercase letter ci meaningthat the letter at the position xi of the secret string is ci . These hints are ordered in theirpositions, i.e., 1 ≤ x1 < · · · < xa ≤ n.
The i-th line of the following b lines contains two integers, yi and hi . It is guaranteed that theysatisfy 2 ≤ y1 < · · · < yb ≤ n and 0 ≤ hi < yi . When hi is not 0, the substring of the secretstring starting from the position yi with the length yi+1 −yi (or n+1−yi when i = b) is identicalto the substring with the same length starting from the position hi . Lines with hi = 0 does nottell any hints except that yi in the line indicates the end of the substring specified in the line
immediately above.
Each of the following q lines has an integer zi (1 ≤ zi ≤ n), specifying the position of the letterin the secret string to output.
It is ensured that there exists at least one secret string that matches all the given information.
In other words, the given hints have no contradiction.

23

Output
The output should be a single line consisting only of q characters. The character at position i ofthe output should be the letter at position zi of the the secret string if it is uniquely determinedfrom the hints, or ? otherwise.
Sample Input 1

Sample Output 1

9 4 5 4
3 C
4 I
7 C
9 P
2 1
4 0
6 2
7 0
8 4
8
1
9
6

ICPC

Sample Input 2

Sample Output 2

1000000000 1 1 2
20171217 A
3 1
42987654321?A

24

ACM International Collegiate Programming Contest
Asia Regional Contest, Tsukuba, 2017–12–17

Problem K
Counting Cycles
Time Limit: 4 seconds
Given an undirected graph, count the number of simple cycles in the graph. Here, a simple cycle
is a connected subgraph all of whose vertices have degree exactly two.

Input
The input consists of a single test case of the following format.
nm
u1 v1
..
.
um vm
A test case represents an undirected graph G.
The first line shows the number of vertices n (3 ≤ n ≤ 100 000) and the number of edges m(n − 1 ≤ m ≤ n + 15). The vertices of the graph are numbered from 1 to n.
The edges of the graph are specified in the following m lines. Two integers ui and vi in thei-th line of these m lines mean that there is an edge between vertices ui and vi . Here, you canassume that ui < vi and thus there are no self loops.
For all pairs of i and j (i 6= j), either ui 6= uj or vi 6= vj holds. In other words, there are noparallel edges.
You can assume that G is connected.

OutputThe output should be a line containing a single number that is the number of simple cycles in
the graph.
Sample Input 1

Sample Output 1

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

3

25

Sample Input 2

Sample Output 2

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

3

Sample Input 3

Sample Output 3

4 6
1 2
1 3
1 4
2 3
2 4
3 4

7

26