package main import ( "bufio" "fmt" "os" ) func main() { in := bufio.NewReader(os.Stdin) out := bufio.NewWriter(os.Stdout) defer out.Flush() var n, m int fmt.Fscan(in, &n, &m) color := make([][]int, n) // [left,right] for i := 0; i < n; i++ { var l, r int fmt.Fscan(in, &l, &r) color[i] = []int{l, r} } isOverlapped := func(left1, right1, left2, right2 int) bool { start := max(left1, left2) end := min(right1, right2) return start <= end } // n个命题分别为[第i个砖块不旋转] // 每两个之间验证四种情况 ts := NewTwoSat(n) for i := 0; i < n; i++ { left1, right1 := color[i][0], color[i][1] revLeft1, revRight1 := m-1-right1, m-1-left1 for j := i + 1; j < n; j++ { left2, right2 := color[j][0], color[j][1] revLeft2, revRight2 := m-1-right2, m-1-left2 // 1. 两个砖块都不旋转 if isOverlapped(left1, right1, left2, right2) { ts.AddNand(i, j) } // 2. 第一个砖块旋转,第二个砖块不旋转 if isOverlapped(revLeft1, revRight1, left2, right2) { ts.AddNand(ts.Rev(i), j) } // 3. 第一个砖块不旋转,第二个砖块旋转 if isOverlapped(left1, right1, revLeft2, revRight2) { ts.AddNand(i, ts.Rev(j)) } // 4. 两个砖块都旋转 if isOverlapped(revLeft1, revRight1, revLeft2, revRight2) { ts.AddNand(ts.Rev(i), ts.Rev(j)) } } } _, ok := ts.Solve() if !ok { fmt.Fprintln(out, "NO") return } fmt.Fprintln(out, "YES") } type TwoSat struct { sz int scc *StronglyConnectedComponents } func NewTwoSat(n int) *TwoSat { return &TwoSat{sz: n, scc: NewStronglyConnectedComponents(n + n)} } // u -> v <=> !v -> !u func (ts *TwoSat) AddIf(u, v int) { ts.scc.AddEdge(u, v) ts.scc.AddEdge(ts.Rev(v), ts.Rev(u)) } // u or v <=> !u -> v func (ts *TwoSat) AddOr(u, v int) { ts.AddIf(ts.Rev(u), v) } // u nand v <=> u -> !v func (ts *TwoSat) AddNand(u, v int) { ts.AddIf(u, ts.Rev(v)) } // u <=> !u -> u func (ts *TwoSat) SetTrue(u int) { ts.scc.AddEdge(ts.Rev(u), u) } // !u <=> u -> !u func (ts *TwoSat) SetFalse(u int) { ts.scc.AddEdge(u, ts.Rev(u)) } func (ts *TwoSat) Rev(u int) int { if u >= ts.sz { return u - ts.sz } return u + ts.sz } func (ts *TwoSat) Solve() (res []bool, ok bool) { ts.scc.Build() res = make([]bool, ts.sz) for i := 0; i < ts.sz; i++ { if ts.scc.Comp[i] == ts.scc.Comp[ts.Rev(i)] { return } res[i] = ts.scc.Comp[i] > ts.scc.Comp[ts.Rev(i)] } ok = true return } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } type Edge struct{ from, to int } type StronglyConnectedComponents struct { G [][]Edge // 原图 Dag [][]Edge // 强连通分量缩点后的顶点和边组成的DAG Comp []int //每个顶点所属的强连通分量的编号 Group [][]int // 每个强连通分量所包含的顶点 rg [][]Edge order []int used []bool } func NewStronglyConnectedComponents(n int) *StronglyConnectedComponents { return &StronglyConnectedComponents{G: make([][]Edge, n)} } func (scc *StronglyConnectedComponents) AddEdge(from, to int) { scc.G[from] = append(scc.G[from], Edge{from, to}) } func (scc *StronglyConnectedComponents) Build() { scc.rg = make([][]Edge, len(scc.G)) for i := range scc.G { for _, e := range scc.G[i] { scc.rg[e.to] = append(scc.rg[e.to], Edge{e.to, e.from}) } } scc.Comp = make([]int, len(scc.G)) for i := range scc.Comp { scc.Comp[i] = -1 } scc.used = make([]bool, len(scc.G)) for i := range scc.G { scc.dfs(i) } for i, j := 0, len(scc.order)-1; i < j; i, j = i+1, j-1 { scc.order[i], scc.order[j] = scc.order[j], scc.order[i] } ptr := 0 for _, v := range scc.order { if scc.Comp[v] == -1 { scc.rdfs(v, ptr) ptr++ } } dag := make([][]Edge, ptr) for i := range scc.G { for _, e := range scc.G[i] { x, y := scc.Comp[e.from], scc.Comp[e.to] if x == y { continue } dag[x] = append(dag[x], Edge{x, y}) } } scc.Dag = dag scc.Group = make([][]int, ptr) for i := range scc.G { scc.Group[scc.Comp[i]] = append(scc.Group[scc.Comp[i]], i) } } // 获取顶点k所属的强连通分量的编号 func (scc *StronglyConnectedComponents) Get(k int) int { return scc.Comp[k] } func (scc *StronglyConnectedComponents) dfs(idx int) { tmp := scc.used[idx] scc.used[idx] = true if tmp { return } for _, e := range scc.G[idx] { scc.dfs(e.to) } scc.order = append(scc.order, idx) } func (scc *StronglyConnectedComponents) rdfs(idx int, cnt int) { if scc.Comp[idx] != -1 { return } scc.Comp[idx] = cnt for _, e := range scc.rg[idx] { scc.rdfs(e.to, cnt) } }