Go: package main

import (
    "bufio"
    "os"
    "fmt"
)

var sc = bufio.NewScanner(os.Stdin)

/**************  Cell  *****************/
type Cell struct {
    item interface{}
    next *Cell
    prev *Cell
}

func NewCell(x interface{}, ne *Cell, pr *Cell) *Cell {
    newCp := new(Cell)
    newCp.item = x
    newCp.next = ne
    newCp.prev = pr
    return newCp
}
/************  End Cell  ***************/

/**************  Queue  ****************/
type Queue struct {
    size int
    front *Cell
    rear *Cell
}

func NewQueue() *Queue {
    return new(Queue)
}

func (q *Queue) Push(x interface{}) {
    newNode := NewCell(x, nil, nil)
    if q.size == 0 {
        q.front = newNode
        q.rear = newNode
    } else {
        newNode.prev = q.rear
        q.rear.next = newNode
        q.rear = newNode
    }
    q.size++
}

func (q *Queue) PopLeft() interface{} {
    if q.size == 0 {
        return nil
    } else {
        x := q.front.item
        if q.size == 1 {
            q.front = nil
            q.rear = nil
        } else {
            q.front = q.front.next
            q.front.prev = nil
        }
        q.size--
        return x
    }
}

func (q *Queue) IsEmpty() bool {
    return q.size == 0
}

func (q *Queue) Length() int {
    return q.size
}

type State struct {
    color string
    cnt int
}

func main() {
    for {
        sc.Scan()
        init := sc.Text()
        if init == "0" {
            break
        }
        bfs(init)
    }
}

func bfs(init string) {
    dic := make(map[string]int)
    que := NewQueue()
    que.Push(State{init, 0})
    length := len(init)
    isSolved := false
    for !que.IsEmpty() {
        state := que.PopLeft().(State)
        _, ok := dic[state.color]
        if ok {
            continue
        } else {
            dic[state.color] = state.cnt
        }

        if isSingleColor(state.color) {
            fmt.Println(state.cnt)
            isSolved = true
            break
        }

        for i := 0;i < length - 1; i++ {
            color1, color2 := string(state.color[i]), string(state.color[i + 1])
            if color1 != color2 {
                color3 := other(color1, color2)
                if i <= length - 2 {
                    que.Push(State{state.color[:i] + color3 + state.color[i + 2:], state.cnt + 1})
                } else {
                    que.Push(State{state.color[:i] + color3, state.cnt + 1})
                }
            }
        }
    }
    if !isSolved {
        fmt.Println("NA")
    }
}

func other(color1, color2 string) string {
    if color1 == "r" {
        if color2 == "g" {
            return "bb"
        } else if color2 == "b" {
            return "gg"
        }
    } else if color1 == "g" {
        if color2 == "r" {
            return "bb"
        } else if color2 == "b" {
            return "rr"
        }
    } else if color1 == "b" {
        if color2 == "r" {
            return "gg"
        } else if color2 == "g" {
            return "rr"
        }
    }
    return ""
}

func isSingleColor(color string) bool {
    for _, c := range color {
        if string(c) != string(color[0]) {
            return false
        }
    }
    return true
}

C++: #include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
#include<map>
#include<queue>

using namespace std;

#define rep(i,n) for(int i=0;i<int(n);i++)
#define reps(i,n) for(int i=1;i<=int(n);i++)

class S{
public:
  string s;
  int n;
  S(string s,int n):s(s),n(n){}
};

int main(){
  while(1){
    string a;
    cin>>a;
    if(a=="0")break;

    queue<S> que;
    map<string,int> memo;
    char cc[111][111];
    rep(i,111)rep(j,111)cc[i][j]=-1;
    que.push(S(a,0));
    int ans=0;
    int kn=0;
    while(1){
      if(que.empty()==1){
	break;
      }
      S u = que.front();
      que.pop();
      ans=u.n;
      //cout<<u.s<<" "<<u.n<<endl;
      if(memo[u.s]!=0){
	continue;
      }
      memo[u.s]=1;
      int comp=1;
      int ch=u.s[0];
      reps(i,u.s.size()-1){
	if(ch!=u.s[i]){
	  comp=0;
	  break;
	}
      }
      if(comp==1){
	kn=1;
	break;
      }
      cc['r']['g']=cc['g']['r']='b';
      cc['r']['b']=cc['b']['r']='g';
      cc['b']['g']=cc['g']['b']='r';
      rep(i,u.s.size()-1){
	string cop=u.s;
	if(u.s[i]!=u.s[i+1]){
	  cop[i]=cop[i+1]=cc[cop[i]][cop[i+1]];
	  que.push(S(cop,u.n+1));
	}
      }
    }
    if(kn==1){
      printf("%d\n",ans);
    }else{
      printf("-1\n");
    }
  }
}

C++: #include <iostream>
#include <string>
#include <queue>
#include <map>

using namespace std;
typedef pair<string, int> P;

void solve()
{
	string str;
	while(cin >> str)
	{
		if(str == "0")
		{
			break;
		}
		bool flag = true;
		for(int j = 0; j < str.size() - 1; ++j)
		{
			if(str[j] != str[j + 1])
			{
				flag = false;
				break;
			}
		}
		if(flag)
		{
			cout << 0 << endl;
			continue;
		}
		queue<P> Que;
		Que.push(make_pair(str, 0));
		queue<P> NextQue;
		map<string, int> Map;
		int step = 0;
		while(true)
		{
			if(step == str.size())
			{
				cout << "NA" << endl;
				break;
			}
			while(!Que.empty())
			{
				for(int i = 0; i < str.size() - 1; ++i)
				{
					string body = Que.front().first;
					if(body[i] == 'b' && body[i + 1] == 'g')
					{
						body[i] = body[i + 1] = 'r';
					}
					else if(body[i] == 'b' && body[i + 1] == 'r')
					{
						body[i] = body[i + 1] = 'g';
					}
					else if(body[i] == 'g' && body[i + 1] == 'b')
					{
						body[i] = body[i + 1] = 'r';
					}
					else if(body[i] == 'g' && body[i + 1] == 'r')
					{
						body[i] = body[i + 1] = 'b';
					}
					else if(body[i] == 'r' && body[i + 1] == 'b')
					{
						body[i] = body[i + 1] = 'g';
					}
					else if(body[i] == 'r' && body[i + 1] == 'g')
					{
						body[i] = body[i + 1] = 'b';
					}
					bool flag = true;
					for(int j = 0; j < str.size() - 1; ++j)
					{
						if(body[j] != body[j + 1])
						{
							flag = false;
							break;
						}
					}
					if(flag)
					{
						cout << Que.front().second + 1 << endl;
						goto NEXT;
					}
					if(!Map[body])
					{
						NextQue.push(make_pair(body, Que.front().second + 1));
					}
					Map[body]++;
				}
				Que.pop();
			}
			while(!NextQue.empty())
			{
				Que.push(NextQue.front());
				NextQue.pop();
			}
			++step;
		}
NEXT:
		;
	}
}

int main()
{
	solve();
	return(0);
}

C++: #include<iostream>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
struct Data{
    string s;
    int t;
    Data(string _s,int _t){
        s =_s,t =_t;
    }
};
int main(){
    string str;
    while(cin>>str,str!="0"){
        queue<Data> Q;
        map<string,bool> M;
        Q.push(Data(str,0));
        while(!Q.empty()){
            Data E = Q.front();
            //cout<<E.s<<endl;
            Q.pop();
            if(M[E.s])continue;
            M[E.s] = true;
            bool flg = true;
            for(int i = 1;i < E.s.length();i++){
                if(E.s[i] != E.s[0])flg = false;
            }
            if(flg){
                cout<<E.t<<endl;
                goto e;
            }
            for(int i = 0;i < E.s.length()-1;i++){
                Data D = E;
                if(D.s[i]!=D.s[i+1]){
                    bool flg[3]={};
                    string w = "rgb";
                    if(D.s[i]=='r'||D.s[i+1]=='r')flg[0] = true;
                    if(D.s[i]=='g'||D.s[i+1]=='g')flg[1] = true;
                    if(D.s[i]=='b'||D.s[i+1]=='b')flg[2] = true;
                    for(int j = 0;j < 3;j++){
                        if(!flg[j])D.s[i] = D.s[i+1] = w[j];
                    }
                    D.t++;
                    //cout<<D.s<<endl;
                    Q.push(D);
                }
            }
        }
        cout<<"NA"<<endl;
        e:;
    }
}