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<iostream>
#include<queue>
#include<map>
using namespace std;
#define rep(i,n) for(int i = 0 ; i < (n) ; ++i )
bool same(string s){
  rep(i,s.size()-1) if(s[i] != s[i+1]) return false;
  return true;
}
char change(char a,char b){
  if(a != 'b' && b != 'b') return 'b';
  if(a != 'g' && b != 'g') return 'g';
  return 'r';
}
int bfs(string s){
  queue<string>que;
  que.push(s);
  map<string,int> used;
  used[s] = 0;
  while(!que.empty()){
    string s = que.front(); que.pop();
    if(same(s)) return used[s];
    rep(i,s.size()-1){
      if(s[i] != s[i+1]){
        string next = s;
        next[i] = next[i+1] = change(next[i],next[i+1]);
        if(!used[next]) que.push(next) , used[next] = used[s] + 1;
      }
    }
  }
  return -1;
}
int main(){
  string s;
  while(cin >> s , s != "0"){
    int ans = bfs(s);
    if(ans == -1) cout << "NA" << endl;
    else cout << ans << endl;
  }
}

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

using namespace std;

typedef pair<string,int> P;

int main() {
	string str;
	char col[3]={'r','g','b'};

	while(cin>>str,str[0]!='0') {
		queue<P> que;
		map<string,bool> mp;

		mp[str]=true;
		que.push(P(str,0));
		int ans=-1;
		while(!que.empty()) {
			P p=que.front();
			que.pop();
			int len=p.first.length();
			bool f=true;
			for(int i=0;i<len-1;i++) {
				if(p.first[i]!=p.first[i+1]) {
					f=false;
					pair<int,int> tmp(p.first[i],p.first[i+1]);
					for(int j=0;j<3;j++) {
						if(p.first[i]!=col[j]&&p.first[i+1]!=col[j]) {
							p.first[i]=p.first[i+1]=col[j];
							break;
						}
					}
					if(mp[p.first]==false) {
						mp[p.first]=true;
						que.push(P(p.first,p.second+1));
					}
					p.first[i]=tmp.first;
					p.first[i+1]=tmp.second;
				}
			}
			if(f) {ans=p.second;break;}
		}
		if(ans==-1) {
			cout<<"NA"<<endl;
		}else {
			cout<<ans<<endl;
		}
	}
}

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

char change (char c1, char c2);
bool simple_check(std::string str); 
void bfs(std::string str); 


int main(void) {
    std::string str; 

    std::cin >> str;
    while (str != "0") {
        bfs(str); 
        std::cin >> str;
    }

    return 0;
}

char change (char c1, char c2) {
    char new_c;
    if (c1 != 'r' && c2 != 'r') {
        new_c = 'r'; 
    } else if (c1 != 'g' && c2 != 'g') {
        new_c = 'g'; 
    } else if (c1 != 'b' && c2 != 'b') {
        new_c = 'b'; 
    } else {
        std::cerr << "????????????" << std::endl;
    }
    return new_c;
}

bool simple_check(std::string str) {
    bool flag = true;
    for (int i = 0; i < str.size() - 1; i++) {
        if (str[i] != str[i + 1]) {
            flag = false;
        }
    }
    return flag;
}

void bfs(std::string str) {
    std::pair<std::string, int> now;
    std::queue<std::pair<std::string, int> > que; 
    std::set<std::string> st; 

    //use in while loop
    std::string str_cp;
    char remained_color;

    que.push(std::make_pair(str, 0));
    st.insert(str);


    while (! que.empty()) {
        now = que.front();
        que.pop();

        // ??¨?????????????????????break?????????
        if (simple_check(now.first) == true) {
            std::cout << now.second << std::endl; 
            return;
        }


        for (int i = 0; i < str.size() - 1; i++) {
            str_cp = now.first;
            if (str_cp[i] != str_cp[i + 1]) {
                remained_color = change(str_cp[i], str_cp[i + 1]);
                str_cp[i] = remained_color;
                str_cp[i + 1] = remained_color;
            }
            if (st.count(str_cp) == 0) {
                que.push(std::make_pair(str_cp,now.second + 1)); 
                st.insert(str_cp);
            }
        }
    }

    std::cout << "NA" << std::endl;
    return; 
}