```go
package main

import (
	"bufio"
	"os"
	"strconv"
)

// Op represents a DSU operation for rollback
type Op struct {
	u, v   int
	szV    int
	distU  int
	typeOp int // 0: merge, 1: violation
}

// Edge represents an undirected edge
type Edge struct {
	u, v int
}

// Global DSU and Segment Tree state
var (
	parent              []int
	dist                []int
	sz                  []int
	stack               []Op
	bipartiteViolations int
	tree                [][]Edge
)

// Initialize DSU structures
func initDSU(n int) {
	parent = make([]int, n+1)
	dist = make([]int, n+1)
	sz = make([]int, n+1)
	for i := 1; i <= n; i++ {
		parent[i] = i
		sz[i] = 1
		dist[i] = 0
	}
	// Initial capacity estimate
	stack = make([]Op, 0, n)
	bipartiteViolations = 0
}

// Find with path parity calculation (no path compression)
func find(i int) (int, int) {
	p := 0
	for i != parent[i] {
		p ^= dist[i]
		i = parent[i]
	}
	return i, p
}

// Unite two sets or detect violation
func unite(u, v int) bool {
	rootU, parityU := find(u)
	rootV, parityV := find(v)

	if rootU != rootV {
		// Merge smaller into larger to maintain O(log N) depth
		if sz[rootU] > sz[rootV] {
			rootU, rootV = rootV, rootU
		}
		// Merge rootU -> rootV
		parent[rootU] = rootV
		// We need parity(u->...->rootU->rootV) != parity(v->...->rootV)
		// parityU ^ dist[rootU] ^ parityV = 1
		// dist[rootU] = parityU ^ parityV ^ 1
		oldDist := dist[rootU]
		dist[rootU] = parityU ^ parityV ^ 1
		
		oldSz := sz[rootV]
		sz[rootV] += sz[rootU]
		
		stack = append(stack, Op{u: rootU, v: rootV, szV: oldSz, distU: oldDist, typeOp: 0})
		return true
	} else {
		// In same component, check bipartiteness
		if parityU == parityV {
			bipartiteViolations++
			stack = append(stack, Op{typeOp: 1})
			return true
		}
	}
	return false
}

// Rollback the last operation
func rollback() {
	last := len(stack) - 1
	op := stack[last]
	stack = stack[:last]

	if op.typeOp == 1 {
		bipartiteViolations--
	} else {
		parent[op.u] = op.u
		dist[op.u] = op.distU
		sz[op.v] = op.szV
	}
}

// Add edge to Segment Tree covering interval [ql, qr]
func addEdgeRange(node, l, r, ql, qr int, e Edge) {
	if ql > r || qr < l {
		return
	}
	if ql <= l && r <= qr {
		tree[node] = append(tree[node], e)
		return
	}
	mid := (l + r) >> 1
	addEdgeRange(node<<1, l, mid, ql, qr, e)
	addEdgeRange(node<<1|1, mid+1, r, ql, qr, e)
}

// DFS on Segment Tree to process queries
func solve(node, l, r int, w *bufio.Writer) {
	ops := 0
	for _, e := range tree[node] {
		if unite(e.u, e.v) {
			ops++
		}
	}

	if l == r {
		if bipartiteViolations == 0 {
			w.WriteString("YES\n")
		} else {
			w.WriteString("NO\n")
		}
	} else {
		mid := (l + r) >> 1
		solve(node<<1, l, mid, w)
		solve(node<<1|1, mid+1, r, w)
	}

	for i := 0; i < ops; i++ {
		rollback()
	}
}

// Fast I/O Scanner
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)
	// Buffer size sufficient for large inputs
	s.Buffer(make([]byte, 1024*1024), 1024*1024)
	return &Scanner{sc: s}
}

func (s *Scanner) NextInt() int {
	s.sc.Scan()
	x, _ := strconv.Atoi(s.sc.Text())
	return x
}

func main() {
	sc := NewScanner()
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	n := sc.NextInt()
	q := sc.NextInt()

	initDSU(n)
	tree = make([][]Edge, 4*q+1)

	// Map to track start times of active edges
	// Key: (u << 32) | v
	active := make(map[uint64]int)

	for i := 1; i <= q; i++ {
		u := sc.NextInt()
		v := sc.NextInt()
		if u > v {
			u, v = v, u
		}
		
		key := uint64(u)<<32 | uint64(v)
		if start, exists := active[key]; exists {
			// Edge removed at query i, active in [start, i-1]
			addEdgeRange(1, 1, q, start, i-1, Edge{u, v})
			delete(active, key)
		} else {
			// Edge added at query i
			active[key] = i
		}
	}

	// Any edges remaining are active until Q
	for key, start := range active {
		u := int(key >> 32)
		v := int(key & 0xFFFFFFFF)
		addEdgeRange(1, 1, q, start, q, Edge{u, v})
	}

	solve(1, 1, q, w)
}
```