【題意】：平面上，一個圓，圓的邊上按順時針放著n個點。現在要連m條邊，比如a，b，那么a到b可以從圓的內部連接，也可以從圓的外部連接。給你的信息中，每個點最多只會連接的一條邊。問能不能連接這m條邊，使這些邊都不相交。

【題解】：題意可能剛開始不是很好理解，比如1和5連邊，2和6連邊，由于點是順序排列的，一畫圖就可以發現，這兩條邊必須一個從圓外面連，一個從內部連，否則就會相交。如果再加入3和7這條邊，那么就必須相交了。
              這樣，我們很容易把問題轉化為一個標準的2-sat問題，把每條邊看成2-sat中的點，i 表示這條邊從圓的內部連邊，i’ 表示從圓的外部連邊。
              如果某兩條邊 i  和 j 有矛盾關系（既只能一個從內部連邊，一個從外部連邊），那么我們可以這樣連邊: i -> j' , i' -> j, j -> i', j' -> i.
              最后判斷一下有無可行解即可。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "vector"
 5 using namespace std;
 6 #define maxn 1050
 7 int n, m;
 8 vector<int> vec[maxn];
 9 int s[maxn], top;
10 int belong[maxn], scc, dfn[maxn], low[maxn], Dindex;
11 bool instack[maxn];
12 struct Line {
13     int a, b;
14 }line[maxn];
15 
16 void dfs(int u) {
17     int v, size = vec[u].size();
18     dfn[u] = low[u] = ++Dindex;
19     instack[u] = true;
20     s[++top] = u;
21     for(int i = 0; i < size; i++) {
22         v = vec[u][i];
23         if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
24         else if(instack[v]) low[u] = min(low[u], dfn[v]);    
25     }
26     if(dfn[u] == low[u]) {
27         scc++;   
28         do {
29             v = s[top--];
30             instack[v] = false;
31             belong[v] = scc;
32         }while(v != u);
33     }
34 }
35 void tarjan() {
36     top = scc = Dindex = 0;
37     memset(dfn, 0, sizeof(dfn));
38     memset(instack, 0, sizeof(instack));
39     for (int u = 0; u < 2 * m; u++)
40         if(!dfn[u]) dfs(u);
41 }
42 
43 bool solvable() {
44     for(int i = 0; i < 2 * m; i += 2) 
45         if(belong[i] == belong[i^1]) return false;
46     return true;
47 }
48 
49 bool conflict(Line a, Line b) {
50     if(a.a > b.b || a.b < b.a || (a.a < b.a && a.b > b.b) || (a.a > b.a && a.b < b.b)) return false;
51     return true;
52 }
53 
54 void build() {
55     for(int i = 0; i < m; i++) {
56         for(int j = i + 1; j < m; j++) {
57             int u = 2 * i, v = 2 * j;
58             if(conflict(line[i], line[j])) {
59                 vec[u].push_back(v^1), vec[u^1].push_back(v);
60                 vec[v].push_back(u^1), vec[v^1].push_back(u);
61             }
62         }
63     }
64 }
65 
66 int main() {
67     for(int i = 0; i < maxn; i++) vec[i].clear();
68     scanf("%d%d", &n, &m);
69     for(int i = 0; i < m; i++) {
70         scanf("%d%d", &line[i].a, &line[i].b);
71         if(line[i].a > line[i].b) swap(line[i].a, line[i].b);
72     }
73     build();
74     tarjan();
75     if(solvable()) printf("panda is telling the truth\n");
76     else printf("the evil panda is lying again\n");
77     return 0;
78 }