【题意】：平面上，一个圆，圆的边上按顺时针放着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 }