merged

7 files changed, 144 insertions, 163 deletions

diff --git a/graph/bellmannFord.cpp b/graph/bellmannFord.cpp
index 7ba51c0..4324886 100644
--- a/graph/bellmannFord.cpp
+++ b/graph/bellmannFord.cpp
@@ -14,6 +14,4 @@ void bellmannFord(int n, vector<edge> edges, int start) {
 		if (dist[e.from] != INF &&
 		    dist[e.from] + e.cost < dist[e.to]) {
 			// Negativer Kreis gefunden.
-	}}
-	//return dist, parent;
-}
+}}} //return dist, parent?;
diff --git a/graph/bronKerbosch.cpp b/graph/bronKerbosch.cpp
index caf2421..ceeb668 100644
--- a/graph/bronKerbosch.cpp
+++ b/graph/bronKerbosch.cpp
@@ -9,7 +9,7 @@ void bronKerboschRec(bits R, bits P, bits X) {
 	if (!P.any() && !X.any()) {
 		cliques.push_back(R);
 	} else {
-		int q = (P | X)._Find_first();
+		int q = min(P._Find_first(), X._Find_first());
 		bits cands = P & ~adj[q];
 		for (int i = 0; i < sz(adj); i++) if (cands[i]){
 			R[i] = 1;
diff --git a/graph/graph.tex b/graph/graph.tex
index f2ad3e7..e299dd7 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -1,33 +1,27 @@
 \section{Graphen}
 
-\begin{algorithm}{DFS}
-	\input{graph/dfs}
-\end{algorithm}
-
-\begin{algorithm}{Minimale Spannbäume}
-	\paragraph{Schnitteigenschaft}
-	Für jeden Schnitt $C$ im Graphen gilt:
-	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
-	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
-	
-	\paragraph{Kreiseigenschaft}
-	Für jeden Kreis $K$ im Graphen gilt:
-	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
-\end{algorithm}
-
-\begin{algorithm}{Kruskal}
-	\begin{methods}[ll]
-		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+\begin{algorithm}{Eulertouren}
+	\begin{methods}
+		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
 	\end{methods}
-	\sourcecode{graph/kruskal.cpp}
+	\sourcecode{graph/euler.cpp}
+	\begin{itemize}
+		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
+		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
+		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
+		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter
+		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
+		Die Existenz muss separat geprüft werden.
+	\end{itemize}
 \end{algorithm}
 
-\begin{algorithm}{Erd\H{o}s-Gallai}
-	Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$
+\begin{algorithm}{Lowest Common Ancestor}
 	\begin{methods}
-		\method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})}
+		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
+		\method{getLCA}{findet LCA}{1}
+		\method{getDepth}{berechnet Distanz zur Wurzel im DFS-Baum}{1}
 	\end{methods}
-	\sourcecode{graph/havelHakimi.cpp}
+	\sourcecode{graph/LCA_sparse.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Centroids}
@@ -37,24 +31,52 @@
 	\sourcecode{graph/centroid.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Heavy-Light Decomposition}
+	\begin{methods}
+		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+	\end{methods}
+	\textbf{Wichtig:} Intervalle sind halboffen
+	
+	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
+	\sourcecode{graph/hld.cpp}
+\end{algorithm}
+\clearpage
+
 \begin{algorithm}{Baum-Isomorphie}
 	\begin{methods}
 		\method{treeLabel}{berechnet kanonischen Namen für einen Baum}{\abs{V}\*\log(\abs{V})}
 	\end{methods}
 	\sourcecode{graph/treeIsomorphism.cpp}
 \end{algorithm}
-\clearpage
 
-\subsection{Kürzeste Wege}
+\begin{algorithm}{Minimale Spannbäume}
+	\paragraph{Schnitteigenschaft}
+	Für jeden Schnitt $C$ im Graphen gilt:
+	Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen.
+	($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.)
+	
+	\paragraph{Kreiseigenschaft}
+	Für jeden Kreis $K$ im Graphen gilt:
+	Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums.
+\end{algorithm}
 
-\subsubsection{Algorithmus von \textsc{Dijkstra}}
-\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})}
-\sourcecode{graph/dijkstra.cpp}
+\begin{algorithm}{Kruskal}
+	\begin{methods}[ll]
+		berechnet den Minimalen Spannbaum & \runtime{\abs{E}\cdot\log(\abs{E})} \\
+	\end{methods}
+	\sourcecode{graph/kruskal.cpp}
+\end{algorithm}
+
+\subsection{Kürzeste Wege}
 
 \subsubsection{\textsc{Bellmann-Ford}-Algorithmus}
 \method{bellmanFord}{kürzeste Pfade oder negative Kreise finden}{\abs{V}\*\abs{E}}
 \sourcecode{graph/bellmannFord.cpp}
 
+\subsubsection{Algorithmus von \textsc{Dijkstra}}
+\method{dijkstra}{kürzeste Pfade in Graphen ohne negative Kanten}{\abs{E}\*\log(\abs{V})}
+\sourcecode{graph/dijkstra.cpp}
+
 \subsubsection{\textsc{Floyd-Warshall}-Algorithmus}
 \method{floydWarshall}{kürzeste Pfade oder negative Kreise finden}{\abs{V}^3}
 \begin{itemize}
@@ -64,37 +86,31 @@
 \sourcecode{graph/floydWarshall.cpp}
 
 \subsubsection{Matrix-Algorithmus}
-Sei $d_{ij}$ die Distanzmatrix von $G$, dann gibt $d_{ij}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{ij} = a_{ij} * b_{ij} = \min\{a_{ik} + b_{kj}\}$
+Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \min\{a_{ik} + b_{k\smash{j}}\}$
 
 
-Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{ij}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{ij} = a_{ij} \* b_{ij} = \sum a_{ik} + b_{kj}$
+Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$
 
-\begin{algorithm}{Lowest Common Ancestor}
+
+\begin{algorithm}{Erd\H{o}s-Gallai}
+	Sei $d_1 \geq \cdots \geq d_{n}$. Es existiert genau dann ein Graph $G$ mit Degreesequence $d$ falls $\sum\limits_{i=1}^{n} d_i$ gerade ist und für $1\leq k \leq n$: $\sum\limits_{i=1}^{k} d_i \leq k\cdot(k-1)+\sum\limits_{i=k+1}^{n} \min(d_i, k)$
 	\begin{methods}
-		\method{init}{baut DFS-Baum über $g$ auf}{\abs{V}\*\log(\abs{V})}
-		\method{getLCA}{findet LCA}{1}
-		\method{getDepth}{berechnet Distanz zur Wurzel im DFS-Baum}{1}
+		\method{havelHakimi}{findet Graph}{(\abs{V}+\abs{E})\cdot\log(\abs{V})}
 	\end{methods}
-	\sourcecode{graph/LCA_sparse.cpp}
+	\sourcecode{graph/havelHakimi.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Heavy-Light Decomposition}
+\begin{algorithm}{Dynamic Connectivity}
 	\begin{methods}
-		\method{get\_intervals}{gibt Zerlegung des Pfades von $u$ nach $v$}{\log(\abs{V})}
+		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
+		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
+		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
 	\end{methods}
-	\textbf{Wichtig:} Intervalle sind halboffen
-	
-	Subbaum unter dem Knoten $v$ ist das Intervall  $[\text{\code{in[v]}},~\text{\code{out[v]}})$.
-	\sourcecode{graph/hld.cpp}
+	\sourcecode{graph/connect.cpp}
 \end{algorithm}
-\clearpage
 
-\begin{algorithm}{Maximal Cliques}
-	\begin{methods}
-		\method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
-		\method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
-	\end{methods}
-	\sourcecode{graph/bronKerbosch.cpp}
+\begin{algorithm}{DFS}
+	\input{graph/dfs}
 \end{algorithm}
 
 \begin{algorithm}{Artikulationspunkte, Brücken und BCC}
@@ -116,6 +132,60 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/2sat.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Maximal Cliques}
+	\begin{methods}
+		\method{bronKerbosch}{berechnet alle maximalen Cliquen}{3^\frac{n}{3}}
+		\method{addEdge}{fügt \textbf{ungerichtete} Kante ein}{1}
+	\end{methods}
+	\sourcecode{graph/bronKerbosch.cpp}
+\end{algorithm}
+\clearpage
+
+\begin{algorithm}{Cycle Counting}
+	\begin{methods}
+		\method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
+		\method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
+	\end{methods}
+	\begin{itemize}
+		\item jeder Zyklus ist das xor von einträgen in \code{base}.
+	\end{itemize}
+	\sourcecode{graph/cycleCounting.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Wert des maximalen Matchings}
+	Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$
+	\sourcecode{graph/matching.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Allgemeines maximales Matching}
+	\begin{methods}
+		\method{match}{berechnet algemeines Matching}{\abs{E}\*\abs{V}\*\log(\abs{V})}
+	\end{methods}
+	\sourcecode{graph/blossom.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
+	\label{kuhn}
+	\begin{methods}
+		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
+	\end{methods}
+	\begin{itemize}
+		\item die ersten [0..n) Knoten in \code{adjlist} sind die linke Seite des Graphen
+	\end{itemize}
+	\sourcecode{graph/maxCarBiMatch.cpp}
+	\begin{methods}
+		\method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}}
+	\end{methods}
+	\sourcecode{graph/hopcroftKarp.cpp}
+\end{algorithm}
+
+\begin{algorithm}{Maximum Weight Bipartite Matching}
+	\begin{methods}
+		\method{match}{berechnet Matching}{\abs{V}^3}
+	\end{methods}
+	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Global Mincut}
 	\begin{methods}
 		\method{stoer\_wagner}{berechnet globalen Mincut}{\abs{V}^2\*\log(\abs{E})}
@@ -178,87 +248,16 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 	\sourcecode{graph/minCostMaxFlow.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Maximal Cardinatlity Bipartite Matching}
-	\label{kuhn}
-	\begin{methods}
-		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
-	\end{methods}
-	\begin{itemize}
-		\item die ersten [0..n) Knoten in \code{adjlist} sind die linke Seite des Graphen
-	\end{itemize}
-	\sourcecode{graph/maxCarBiMatch.cpp}
-	\begin{methods}
-		\method{hopcroft\_karp}{berechnet Matching}{\sqrt{\abs{V}}\*\abs{E}}
-	\end{methods}
-	\sourcecode{graph/hopcroftKarp.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Maximum Weight Bipartite Matching}
-	\begin{methods}
-		\method{match}{berechnet Matching}{\abs{V}^3}
-	\end{methods}
-	\sourcecode{graph/maxWeightBipartiteMatching.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Wert des maximalen Matchings}
-	Fehlerwahrscheinlichkeit: $\left(\frac{m}{MOD}\right)^I$
-	\sourcecode{graph/matching.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Allgemeines maximales Matching}
-	\begin{methods}
-		\method{match}{berechnet algemeines Matching}{\abs{E}\*\abs{V}\*\log(\abs{V})}
-	\end{methods}
-	\sourcecode{graph/blossom.cpp}
-\end{algorithm}
-
-\optional{
-\begin{algorithm}{TSP}
+\begin{algorithm}[optional]{TSP}
 	\begin{methods}
 		\method{TSP}{berechnet eine Tour}{n^2\*2^n}
 	\end{methods}
 	\sourcecode{graph/TSP.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Bitonic TSP}
+\begin{algorithm}[optional]{Bitonic TSP}
 	\begin{methods}
 		\method{bitonicTSP}{berechnet eine Bitonische Tour}{n^2}
 	\end{methods}
 	\sourcecode{graph/bitonicTSPsimple.cpp}
 \end{algorithm}
-}
-
-\begin{algorithm}{Cycle Counting}
-	\begin{methods}
-		\method{findBase}{berechnet Basis}{\abs{V}\cdot\abs{E}}
-		\method{count}{zählt Zykel}{2^{\abs{\mathit{base}}}}
-	\end{methods}
-	\begin{itemize}
-		\item jeder Zyklus ist das xor von einträgen in \code{base}.
-	\end{itemize}
-	\sourcecode{graph/cycleCounting.cpp}
-\end{algorithm}
-
-\begin{algorithm}{Eulertouren}
-	\begin{methods}
-		\method{euler}{berechnet den Kreis}{\abs{V}+\abs{E}}
-	\end{methods}
-	\sourcecode{graph/euler.cpp}
-	\begin{itemize}
-		\item Zyklus existiert, wenn jeder Knoten geraden Grad hat (ungerichtet),\\ bei jedem Knoten Ein- und Ausgangsgrad übereinstimmen (gerichtet).
-		\item Pfad existiert, wenn genau $\{0, 2\}$ Knoten ungeraden Grad haben (ungerichtet),\\ bei allen Knoten Ein- und Ausgangsgrad übereinstimmen oder einer eine Ausgangskante mehr hat (Startknoten) und einer eine Eingangskante mehr hat (Endknoten).
-		\item \textbf{Je nach Aufgabenstellung überprüfen, wie ein unzusammenhängender Graph interpretiert werden sollen.}
-		\item Wenn eine bestimmte Sortierung verlangt wird oder Laufzeit vernachlässigbar ist, ist eine Implementierung mit einem \code{vector<set<int>> adjlist} leichter
-		\item \textbf{Wichtig:} Algorithmus schlägt nicht fehl, falls kein Eulerzyklus existiert.
-		Die Existenz muss separat geprüft werden.
-	\end{itemize}
-\end{algorithm}
-
-\begin{algorithm}{Dynamic Connectivity}
-	\begin{methods}
-		\method{Constructor}{erzeugt Baum ($n$ Knoten, $m$ updates)}{n+m}
-		\method{addEdge}{fügt Kannte ein,\code{id}=delete Zeitpunkt}{\log(n)}
-		\method{eraseEdge}{entfernt Kante \code{id}}{\log(n)}
-	\end{methods}
-	\sourcecode{graph/connect.cpp}
-\end{algorithm}
diff --git a/graph/havelHakimi.cpp b/graph/havelHakimi.cpp
index 8d5d6ab..6246fe0 100644
--- a/graph/havelHakimi.cpp
+++ b/graph/havelHakimi.cpp
@@ -5,14 +5,12 @@ vector<vector<int>> havelHakimi(const vector<int>& deg) {
 	while (!pq.empty()) {
 		auto [degV, v] = pq.top(); pq.pop();
 		if (sz(pq) < degV) return {}; //impossible
-		vector<pair<int, int>> todo;
-		for (int i = 0; i < degV; i++) {
-			auto [degU, v] = pq.top(); pq.pop();
+		vector<pair<int, int>> todo(degV);
+		for (auto& e : todo) e = pq.top(), pq.pop();
+		for (auto [degU, u] : todo) {
 			adj[v].push_back(u);
 			adj[u].push_back(v);
-			if (degU > 1) todo.push_back({degU - 1, u});
-		}
-		for (auto e : todo) pq.push(e);
-	}
+			if (degU > 1) pq.push({degU - 1, u});
+	}}
 	return adj;
 }
diff --git a/graph/kruskal.cpp b/graph/kruskal.cpp
index 5b0e153..d21da01 100644
--- a/graph/kruskal.cpp
+++ b/graph/kruskal.cpp
@@ -1,6 +1,6 @@
 sort(all(edges));
 vector<edge> mst;
-int cost = 0;
+ll cost = 0;
 for (edge& e : edges) {
 	if (findSet(e.from) != findSet(e.to)) {
 		unionSets(e.from, e.to);
diff --git a/graph/matching.cpp b/graph/matching.cpp
index ddd1c81..2deb672 100644
--- a/graph/matching.cpp
+++ b/graph/matching.cpp
@@ -1,32 +1,9 @@
 constexpr int MOD=1'000'000'007, I=10;
 vector<vector<ll>> adjlist, mat;
 
-int gauss(int n, ll p) {
-	int rank = n;
-	for (int line = 0; line < n; line++) {
-		int swappee = line;
-		while (swappee < n && mat[swappee][line] == 0) swappee++;
-		if (swappee == n) {rank--; continue;}
-		swap(mat[line], mat[swappee]);
-		ll factor = powMod(mat[line][line], p - 2, p);
-		for (int i = 0; i < n; i++) {
-			mat[line][i] *= factor;
-			mat[line][i] %= p;
-		}
-		for (int i = 0; i < n; i++) {
-			if (i == line) continue;
-			ll diff = mat[i][line];
-			for (int j = 0; j < n; j++) {
-				mat[i][j] -= (diff * mat[line][j]) % p;
-				mat[i][j] %= p;
-				if (mat[i][j] < 0) mat[i][j] += p;
-	}}}
-	return rank;
-}
-
 int max_matching() {
 	int ans = 0;
-	mat.assign(sz(adjlist), vector<ll>(sz(adjlist)));
+	mat.assign(sz(adjlist), {});
 	for (int _ = 0; _ < I; _++) {
 		for (int i = 0; i < sz(adjlist); i++) {
 			mat[i].assign(sz(adjlist), 0);
@@ -35,7 +12,12 @@ int max_matching() {
 					mat[i][j] = rand() % (MOD - 1) + 1;
 					mat[j][i] = MOD - mat[i][j];
 		}}}
-		ans = max(ans, gauss(sz(adjlist), MOD)/2);
+		gauss(sz(adjlist), MOD); //LGS unten
+		int rank = 0;
+		for (auto& row : mat) {
+			if (*min_element(all(row)) != 0) rank++;
+		}
+		ans = max(ans, rank / 2);
 	}
 	return ans;
 }
diff --git a/graph/minCostMaxFlow.cpp b/graph/minCostMaxFlow.cpp
index 27f6b34..d6d0586 100644
--- a/graph/minCostMaxFlow.cpp
+++ b/graph/minCostMaxFlow.cpp
@@ -23,13 +23,15 @@ struct MinCostFlow {
 	}
 
 	bool SPFA() {
-		pref.assign(sz(adjlist), - 1);
+		pref.assign(sz(adjlist), -1);
 		dist.assign(sz(adjlist), INF);
 		vector<bool> inqueue(sz(adjlist));
 		queue<int> queue;
 
-		dist[s] = 0; queue.push(s);
-		pref[s] = s; inqueue[s] = true;
+		dist[s] = 0;
+		queue.push(s);
+		pref[s] = s;
+		inqueue[s] = true;
 
 		while (!queue.empty()) {
 			int cur = queue.front(); queue.pop();
@@ -39,9 +41,11 @@ struct MinCostFlow {
 				if (edges[id].f > 0 &&
 				    dist[to] > dist[cur] + edges[id].cost) {
 					dist[to] = dist[cur] + edges[id].cost;
-					pref[to] = cur; con[to] = id;
+					pref[to] = cur;
+					con[to] = id;
 					if (!inqueue[to]) {
-						inqueue[to] = true; queue.push(to);
+						inqueue[to] = true;
+						queue.push(to);
 		}}}}
 		return pref[t] != -1;
 	}