Link to question: question
Link to editorial: editorial
The editorial states that “If the first and last cows are the same breed, this graph will always output N-1 as the shortest path, which may be incorrect if this breed doesn’t talk to itself.” Could someone explain why the BFS would always output N-1 in this case?
Thanks 
Well hi, it’s me again. Let me begin by apologizing for my dumb mistake : I misunderstood you badly. That day when I make my first reply to this post, I thought your question was “If the first and the last cow are of the same breed and they are allow to communicate, why do we have N-1 for an answer” and take it lightly. Upon going to bed, I even thought “If that guy can’t answer such question, why was he doing USACO Gold ?” and today, that question suddenly return to my head. I realized something was off (well it’s sus when we see one guy who can’t answer that question doing Gold problems right ?). Don’t worry though, now I’ve returned to atone my sin 
. To answer your question, you need to look at the way we do BFS, the way we take the answer to be exact : dist[0][N]. Only now we see the question : “Why must we use a fake breed for the N-th cow ?”. It stated clearly in the editorial that we using BFS to “mimic” the traveling signal. The distance between the i-th and the j-th cow is | i - j |, meaning the signal travel at the speed of 1 cow per timestep, and we decide where will the signal goes using the breed of the last sender. dist[B][i] mean the shortest distance from the first cow, and the last sender belong to the B breed. Now take a look at we start the BFS by pushing the information consist of the first cow location, which is 1, and it’s breed, which is breeds[1] in the editorial. Imagine if the first and the last cow belong to the same breed, and we take the answer like normal, aka without the fake breed 0 : dist[breed[N]][N] and now we have one BIG problem : if the last cow can’t actually be reached by any other breed (not even it own) then we are left with the fake answer from the “floating” signal in our deque (look at the first two if statements in the BFS part and you will see that we get our answer if the signal can be “captured” at the last cow’s location, otherwise, it’s “floating” and can’t be use. The 0-1BFS cleverly avoid taking false answer by pushing the “captured” signal to the front, so we won’t have to deal with an annoying WA verdict (notice we only process dist[b][j] if dist[b][j] != -1)). The after math is easy though, if we take dist[breed[N]][N] as answer, we will have the wrong signal come from the first cow, which belong to the same breed as the N-th. For the proof why we “capture” signal along is way, please refer to the last paragraph of the editorial (it’s just me or the editorial for USACO is always really complicated and hard to understand, in comparison to Codeforces ?).
EDIT: Well I know you will likely read this in 2022 so Happy New Year to you, and again, sorry for the mistake
Thank you!!! Happy new year to you too 