Indonesian children like to play with rubber bands, partly because they are very widely available, and partly because a lot of villagers could not afford modern, more expensive toys for their kids. The original shape of the rubber band is a simple circle like in Figure 1. Figure 2 and 3 are some origami kids can make with rubber bands. There are only two kinds of basic transformations of a rubber band: 1. Self-loop 2. Passing The two transformations, when repeated multiple times on different parts of the rubber band, can yield any of the valid origami. Now your task is to detect whether a given origami is possible or impossible to be formed from the original rubber band shape. The description of the origami is as follows. Suppose the rubber band has length L, and points in the rubber band is marked 0, 1, 2, ..., L−1, as illustrated on the right. Then the origami can be described with exactly P pairs (Ai, Bi) of distinct numbers, such that when the origami is placed in a flat plane and looked at from the top of the plane, position Ai in the rubber band overlaps and occludes (is at the front of) position Bi. Given the description of the overlappings of the flattened origami as seen from the top, determine whether the origami position is reachable from the original shape of the rubber band.
2/3 Input The first line of input contains an integer T (T ≤ 100) denoting the number of cases. The first line of each case contains two integers, L (1 ≤ L ≤ 1,000,000) and P (1 ≤ P ≤ 5,000) as defined by the problem statement. The next P lines each contains Ai and Bi (0 ≤ Ai,Bi < L). A blank line follows the last line in each case. The input is guaranteed to satisfy these conditions: • A position in an origami is mentioned in at most one pair with some other position, describing a unique overlap. • The origami represented by the input is planar, that is, the overlappings result from the origami being flattened on a plane. Output For each case, output ‘Case #X: Y ’, where X is case number starts from 1 and Y is either a ‘YES’ or a ‘NO’ (without quotes). A ‘YES’ indicates that the origami is possible to be formed from the original shape of the rubber band. A ‘NO’ indicates otherwise. The following 3 figures correspond to sample input. Sample Input 3 20 5 08 2 10 4 12 15 5 18 7 50 7 10 42 28 15 27 39 18 31 38 32 21 37 24 34 20 5
3/3 08 10 2 4 12 15 5 7 18 Sample Output Case #1: YES Case #2: YES Case #3: NO